不使用数组递归创建所有子集

Question

我们从用户那里得到非负整数 n，我们必须打印集合 ({1,2,3,...,n}) 的所有子集。 (n<=20)

例如 n=3 我们必须打印：

{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}

,s 是可选的，序列可以不带任何逗号打印。（如 {1 2 3}）我必须补充一点，子集的顺序必须与示例完全相同。意思首先是有 1 的子集，然后是有 2 的子集和...。必须首先打印最长的子集。（从最大子集（集合本身）到空集的字典顺序）

我在网上看到很多代码都是用数组或者用位数组来表示我们是否使用数字来解决这个问题的。问题是，在这个问题中，我们不允许使用任何类型的数组或其他数据结构，如 vector 等。即使使用像字符串这样的数组行为也是完全禁止的。只能用递归来解决。

我们也不允许使用任何高级功能。例如，如果我们用 C 编写它，我们只允许使用 stdio.h 或 C++，只允许 <iostream> 而不允许其他库。

我不知道在没有任何数组的情况下该怎么做。如何检查它必须打印哪个数字，同时管理 {}.

PS1。问题只是具有这些条件的发电功率组：

完全禁止使用数组、字符串和偶数循环。只是递归。

用户 Kosyr 使用位运算符提交了一个非常好的答案。所以如果你想提交另一个答案，提交一个甚至不使用位运算符的答案。

PS2.

我在 George 的帮助下编写了这段代码，但它运行不正常。它没有像 1 2 4 这样的东西。它也重复了一些情况。

#include <stdio.h>


void printAllSets (int size)
  {printRows (size, 1);}

void printRows (int size , int start)
{
  if (start<=size)
  {printf( "{ ");
  printRow (start, size);
  printf ("}");
  printf ("\n");}
  if (start <= size)
  {printRows(size -1 , start);
    printRows (size , (start + 1));}
}
printRow (int start, int limit)
{

  if (start <= limit)
  {

    printf ("%d ",start);
    printRow (start +1, limit);
  }
}


int main()
{
    printAllSets(5);
    printf("{ }");
    return 0;
}

PS3.

用户 Kosyr 使用位运算符提交了一个非常好的答案。所以如果你想提交另一个答案，提交一个甚至不使用位运算符的答案。

Answer 1

循环的替代方法是递归。

为了解决这个问题（我认为...还没有测试过），我通过将样本日期制成表格来调查问题并辨别出三个状态，Size，Start和Limit 进展如下：

Size  Start Limit   Output
  10      1    10    1..10
  10      1     9     1..9
              ...      ...
  10      1     1        1
  10      2    10    2..10
  10      2     9     2..9
              ...      ...
  10      2     2        2
        ...   ...      ...
  10     10    10       10

以下伪代码中的递归算法可以解决问题：

printAllSets size
  printRows size 1

printRows size start
  print "{"
  printRow start size
  print "}"
  print CRLF
  if start <= size
    printRows size (start + 1)

printRow start limit
  if start <= limit
    print start + SPACE
    printRow start (limit - 1)

希望这至少能帮助您指明正确的方向。

Answer 2

递归算法非常占用内存。这里的算法为n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

第一次递归print枚举k从2^n-1到0，第二次递归bin枚举k的所有位并打印非- 零位。例如，max_bits = 5 和 k = 19 是 10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0，位 4,1,0 互操作为集合 {5-4,5-1,5-0} => {1,4,5}

Answer 3

我认为我们可以迭代解决这个问题，我们可以假设它也可以转换为递归，尽管这似乎没有必要。考虑到我们可以使用常识对给定索引的任何组合进行排序。所以我们需要做的就是计算我们跳过了多少早期的组合，以及在迭代的每个阶段我们需要取消排序的组合（我可能错过了以下内容，但我认为总体思路是合理的）：

Skip 0, unrank from `3 choose 3`
`2 choose 2` combinations
{1 , 2 , 3} 

Skip 0, unrank from `3 choose 2`
`2 choose 1` combinations
{1 , 2}
{1 , 3}

Skip 0, unrank from `3 choose 1`
`2 choose 0` combinations
{1}

Skip `3 choose 2 - 2 choose 2`,
unrank from `3 choose 2`
`1 choose 1` combinations
{2 , 3}

Skip `3 choose 1 - 2 choose 1`,
unrank from `3 choose 1`
`1 choose 0` combinations
{2}

Skip `3 choose 1 - 1 choose 1`,
unrank from `3 choose 1`
`0 choose 0` combinations
{3}

Empty set
{}

Answer 4

根据定义，集合 k、powerset k 的幂集是包含给定集合中元素的所有可能集合的集合，包括空集本身。显然，当 k 是空集时，powerset [] 只是包含空集 [ [] ] 的集合。现在，给定 k、powerset k 的幂集，k 的幂集加上一个附加元素 E、powerset (K+E) 将包括所有可能的集合，其中包含没有 E、powerset k 的元素加上那些相同的元素，除了现在都包含 E

伪代码...

let powerset k =
   match k with
   | [] -> [[]]
   | x:xs -> x * powerset xs + powerset xs

或尾调用等效性能

let powerset k =
   let (*) e ess = map (es -> e::es) ess
   reduce (e ess -> (e * ess) ++ ess) [ [] ] (reverse k)

.....（在 F# 中）

let rec powerset k =
  match k with
  | []    -> [ [] ]
  | x::xs -> 
      let withoutE = powerset xs
      let withE = List.map (fun es -> x::es) withoutE
      List.append withE withoutE

或更简洁

let rec powerset = function
  | []    -> [ [] ]
  | x::xs -> List.append (List.map (fun es -> x::es) (powerset xs)) (powerset xs)

更好的版本将允许尾调用优化...我们使用常见的功能模式实现了这一点：

let rec powerset2 k = 
  let inline (++) a b = List.concat [a;b]
  let inline (+*) a bs = List.map (fun b -> a::b) bs
  List.fold 
    (fun ac a -> (a +* ac) ++ ac)
    [ [] ] 
    (List.rev k)

-- 这让我花了一段时间才重新发现。这是一个有趣的小谜题。 :)

不使用数组递归创建所有子集

Creating all subsets recursively without using array

algorithm

recursion

subset

powerset