算法生成数字组合不重复 | 算法生成数字组合不重复

本文介绍了算法生成数字组合不重复的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我在这里检查几乎每一个类似的帖子，但我无法弄清楚如何我可以做我想做的。我所想就是给输入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:

要更加清晰：如果输入数是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:

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

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.

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