返回给定数字所有可能组合的 C++ 算法

Question

我试图找到所有可能的数字组合。

例如:输入1 2 3 4 5

输出1、2、3、4、5、21,31,32,41,42,43、51,52、53、54、321,421、431、432、521,531,532、541、542、543、4321,5321,5421,5431,5432,54321

(每个数字都应该这样排序——从大到小)

我有一个排序数组。我正在尝试编写这些数字，它工作得很好，但输入多个相同的数字(例如 3 3 2 2 1)时效果不佳。

不好的是，这需要递归。

我的基本算法如下所示:(它更复杂但这是基本结构)

extract(arrWithNumbers, PrintingArray) {

    For(i = 0; 0 < Numbers in array; i++) {
        if (numbers == i + 1) print(PrintingArray);
        PrintingArray[i] = arrWithNumbers[i];
        extract(arrWithNumbers, PrintingArray);
    }
}

是否有任何已知的算法可以帮助我？

它不仅使用

找到所有可能的组合

感谢您的时间和帮助。

Answer 1

示例代码:

#include <stdio.h>

int next_combination(size_t *I, size_t k, size_t n)
{
size_t i, j;
    i = k-1;                            /* find next element to increment */
    while(I[i] == (n-k+i)){
        --i;
        if(i == (size_t)-1){            /* if done */
            for(i = 0; i < k;  i++)     /*  return with initial combination */
                I[i] = i;
            return(0);
        }
    }
    I[i] += 1;                          /* increment element */
    for(j = i+1; j < k; j++)            /* create increasing string */
            I[j] = I[i]+j-i;
    return(1);                          /* return with new combination */
}

int main(int argc, char **argv)
{
int    A[5] = {5, 4, 3, 2, 1};
size_t I[5];
size_t i, k, n;
    n = sizeof(A)/sizeof(A[0]);         /* n things */
    for(k = 1; k <= n; k++){            /* n things k at a time */
        for(i = 0; i < k;  i++)         /* create initial combination */
            I[i] = i;
        do{                             /* display combinations */
            for(i = 0; i < k; i++)
                printf("%2d", A[I[i]]);
            printf("\n");
        }
        while(next_combination(I, k, n));
    }
    return(0);
}