c - 在c中查找唯一的任意大小的数字组合的算法

Question

我需要一个干净的 C 代码来找出数字的组合。 任意数量的数字和任意大小的组合。 例如对于{1,2,3} 输出应为{1,2,3,12,13,23,123}，注意23和32相同。 有没有干净的c 程序？

最诚挚的问候，

Answer 1

有很多方法可以做到这一点。这是一种使用位操作的方法。

设给定集合为a。

这个代码非常小。了解以下内容，您就会了解这一小段代码的工作原理。

在这里您必须意识到的第一件事是您正在查找给定集合的(2ⁿ - 1)子集。

任何集合都有 2ⁿ 个子集，在这里，您排除了 null 集合。因此 (2ⁿ - 1)

现在，为了生成这些子集，我们需要一个算法。

Observe the following:

---

001 --- 1

010 --- 2

011 --- 3

100 --- 4

101 --- 5

110 --- 6

111 --- 7

The left digits constitute the binary representation of the right decimal numbers.

如果我们写出4位二进制数，就会有15种组合。请注意，我排除了上例中所有数字均为零的组合。

一般来说，对于n位个二进制数，有(2ⁿ - 1)种不同的数字组合。我们可以用它以非常简单的方式生成子集。

对于集合中的每个元素，您可以:

1. 选择当前子集的元素。
2. 不要为当前子集选择该元素。
3. 忽略您不选择的情况。

(因此，有(2ⁿ - 1)子集)

现在，我说执行以下操作:

for i in [1,2^n - 1]:
     Let b = binary representation of i.
     for every jth bit in b:
         if the jth bit is set:
             print a[j]
     print a newline character.

这是 C 代码:

// include your headers

int isJthBitSet(int i,int j)  
{
// returns 1 if jth bit is set in the binary representation of i.
    return (i & (1 << j));
}

int main()
{
     int n = 3;               // The size of the set for example. 
     int a[] = {1,2,3};      // the given set, for example.
     for(int i = 1; i < (1 << n); i++)   // i is from 1...2^n - 1
     {
          for(int j = 0; j < n; j++) // for every jth bit in the n-bit representation of i
          {
                if(isJthBitSet(i,j)) // if the bit is set
                    printf("%d ", a[j]); // print the corresponding element
          }
          printf("\n");
     }
    return 0;
}

就这样了。