算法生成数字组合不重复 [英] algorithm for generating number combinations without repetition

问题描述

我在这里检查几乎每一个类似的帖子，但我无法弄清楚如何我可以做我想做的。我所想就是给输入C程序，让说4号，程序返回下面的数字数组中的：

I checked almost every similar post in here but I couldn't figure out how I can do what I want. What I am trying is to give an input in a C program, let say number 4, and the program return the following numbers in an array:

1
2
3
4
12
13
14
23
24
34
123
134
124
1234

要更加清晰： 如果输入数是4，则我想使用数字1-4和产生的数字的所有可能的组合（从1位数字的组合，以4位数字的组合）而无数字重复

To be more clear: If the input number is 4 then i want to use digits 1-4 and generate all the possible combinations of digits(from 1-digit combinations to 4-digit combinations) without digit repetitions.

我尝试以下code：

#include <stdio.h>

/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
    printf("{");
    int i;
    for (i = 0; i < k; ++i)
        printf("%d, ", comb[i] + 1);
    printf("\\b\\b}\\n");
}


    int next_comb(int comb[], int k, int n) {
    int i = k - 1;
    ++comb[i];
    while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
        --i;
        ++comb[i];
    }

    if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
        return 0; /* No more combinations can be generated */

    /* comb now looks like (..., x, n, n, n, ..., n).
    Turn it into (..., x, x + 1, x + 2, ...) */
    for (i = i + 1; i < k; ++i)
        comb[i] = comb[i - 1] + 1;

    return 1;
}

int main(int argc, char *argv[]) {
    int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
    int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
    int comb[16]; /* comb[i] is the index of the i-th element in the
            combination */

    /* Setup comb for the initial combination */
    int i;
    for (i = 0; i < k; ++i)
        comb[i] = i;

    /* Print the first combination */
    printc(comb, k);

    /* Generate and print all the other combinations */
    while (next_comb(comb, k, n))
        printc(comb, k);

    return 0;
}

以上程序输出结果。我想以某种方式得到的结果..但我不能，因为上面的code打印出结果在一个陌生的方式。

The above program prints the result. I want to get the result somehow.. but I can't because the above code prints the result in a strange manner.

推荐答案

我们用INT重新present一组。对于第i位，如果是1的话，我是在集，反之亦然。

We use a int to represent a set. For the i-th bit, if it is 1, then i is in the set and vice versa.

取例如：1010（2）= {4,2} 1111（2）= {4,3,2,1}

Take a example:1010(2)={4,2} 1111(2)={4,3,2,1}

有关每一将要考虑的因素，有两种选择：在或不在集合。

For every element that will be considered, there is two choices: in or not in the set.

因此​​，有2 ^ n个不同的集总。而在我的code，我只列举每一个可能的INT这是对应的一组，并输出相应的设置。

So, there are 2^n different set in total. And in my code, I just enumerate every possible int which is corresponding a set, and output the corresponding set.

所以，我们得到这个code：

So we get this code:

for(int i=1;i<(1<<n);i++)
{
    for(int j=0;j<n;j++)
        if ((1<<j)&i) printf("%d",j+1);
    puts("");
}

当n = 4，输出：

when n=4, output:

1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234

如果你要输出的答案给予的顺序，才使他们的字符串，并把这些字符串中的载体和排序。

If you want to output the answer as the order of giving, just make them string and put these string in vector and sort.

如果n很大，你可以使用的bitset。但N> 30时，它可能不终止于小时。所以int是有效的。

If n is large, you can use bitset. But when n>30,it may not be terminates in hours. So int is efficient.

这篇关于算法生成数字组合不重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！