c++ - 错误生成组合问题的非递归方法

Question

我想要一种非递归方法来解决生成特定字符集或数字组合的问题。

因此，给定数字 n 的子集 k，生成所有可能的组合 n!/k!(n-k)!

给定前一个组合，递归方法将给出一个组合。

非递归方法将生成给定循环索引值 i 的组合。

我用这段代码解决了这个问题:

在 n = 4 和 k = 3 的情况下进行测试，它可以工作，但如果我将 k 更改为大于 3 的数字，它就不起作用。

是不是因为(n-k)!如果 n = 4 且 k = 3 为 1。如果 k > 3，它将大于 1？

谢谢。

int facto(int x);

int len,fact,rem=0,pos=0;
int str[7];
int avail[7];


   str[0] = 1;
   str[1] = 2;
   str[2] = 3;
   str[3] = 4;
   str[4] = 5;
   str[5] = 6; 
   str[6] = 7;




  int tot=facto(n) / facto(n-k) / facto(k);




for (int i=0;i<tot;i++)
{


       avail[0]=1;
       avail[1]=2;
       avail[2]=3;
       avail[3]=4;
       avail[4]=5; 
       avail[5]=6;
avail[6]=7;



    rem = facto(i+1)-1;
    cout<<rem+1<<". ";
    for(int j=len;j>0;j--)
    {
        int div = facto(j); 
        pos = rem / div; 
        rem = rem % div; 
        cout<<avail[pos]<<" "; 
        avail[pos]=avail[j];

    }
    cout<<endl;
}

int facto(int x)
{
    int fact=1;
    while(x>0) fact*=x--;
    return fact;
}

Answer 1

呃..为什么不使用std::next_permutation ？它完全可以满足您的需求，并且不需要您自己编写(以及调试和维护)。