不重复循环

id: not_repeat_permutation

题目

题目描述

有n个重复数字,数字可能重复,又有n个位置,每个位置都可以放一个数字,求

  1. 第一行输出有方案数
  2. 从小到大,按字典序输出所有的方案

样例输入

3
1 1 2

样例输出

1 1 2 
1 2 1 
2 1 1

解析

只针对样例,我们可以这样思考🤔:从3个位置中选2个位置来放1,剩下的1个位置来放2,那么方案数为:C_{3}^{2}

但是面对复杂的数据的时候,有没有一种方法可以生成所有的方案的方法呢?

按下面的方法来操作,可以生成符合题目要求的所有方案

使用代码来描述方法.

代码

1. 设``m``表示不同的数字的数量
2. 建立``m``个桶,相同的数字放到一个桶里,``a[i]``表示第``i``种数字的放到桶里后,桶里数字的数量
3. ``n``个位置,按顺序挑数字,方法如下
  - 第1个位置,从``m``里选一个非空的桶``j``
  - 从桶``j``里拿一下数字放入第1个位置
  - 第2个位置然后在挑选
  - 第3个位置然后在挑选
  - ``\cdots``
  - 第n个位置然后在挑选
4. 重复,回溯操作``3``,就可以生成所有的方案

核心:每个位置只有m种可能性

证明

如何证明上面的方法生成的方案不多不少??? 正好不生成不重复的方案

1(1) 1(2) x
1(2) 1(1) x

使用数学归纳法

当n=1时,也就是只有一个位置时,按上面的方法操作,显然得到答案为m,正确.

f(1,s)=∑1mx(i)f(1,s) = \sum_{1}^{m} x(i)

当n=2时,也就是有2位置时

,使用集合分类的思想,按,我们可以把所有的方案分成以下的几种

核心:第1个位置有m种可能性!!!

为什么每个位置有m种可能性!!!

怎么才能不重复??

1(1) 1(2) x
1(2) 1(1) x

不能出现这种情况?怎么才能不出现???

从一个箱子拿,每个人都拿完,只有一种可能性,证明法:暴力验证. 从2个箱子里拿,不会重复.

f(i,si)=∑imf(i−1,si−1)∣a[i]\geslant1f(i,si) = \sum_{i}^{m} f(i-1,s_{i-1}) | a[i] \geslant 1

有条件的sum的公式,怎么写

数学公式

当前的方案数,与n个数字的状态,(m,a[i]),有关

代码

核心: 把想同的数放到同一个箱子里,每个位置只从每个箱子取一个,可以避免重复

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
int n; //n个数
int m; //m个

int rcd[maxn]; //record记录, 第i桶对应的数字
int b[maxn]; //桶,箱子
int b_idx; //桶记数

int choose[maxn]; //选择的数

//数据读取
void init() {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int j,t;
        std::cin >> t;
        for(j = 1;j <= b_idx ;++j ) // j: 1->b
        {
            if( rcd[j] == t )
            {
                b[j]++;
                break;
            }
        }
        if( j == b_idx+1) { //没有找到
            b_idx++;
            b[b_idx] = 1;
            rcd[b_idx] = t;
        }
    }
}

void not_repeat_permutation(int dep)
{
    if( dep > n) { //到达边界
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            cout << choose[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i =1;i<=b_idx;i++) {
        if( b[i] > 0) {
            b[i]--;
            choose[dep] = rcd[i];
            not_repeat_permutation(dep+1);
            b[i]++;
        }
    }
}


int main () {
    init();
    not_repeat_permutation(1);
    return 0;
}