algorithm - 从未知数量的集合中选择元素

Question

我想列出所有可能的组合，这些组合是从用户输入的一组（未知）集合中选择每个集合中的至少一个和至多所有元素。一个元素可能在多个集合中，但不止一次列出它不是问题。

例如：- 如果用户输入 3 组为

{1,3,5}
{2,4}
{1} 

输出

1,2,1
1,4,1
1,2,4,1
3,2,1
3,4,1
3,2,4,1
5,2,1
5,4,1
5,2,4,1
1,3,2,1
1,3,4,1
1,3,2,4,1
1,5,2,1
1,5,4,1
1,5,2,4,1
3,5,2,1
3,5,4,1
3,5,2,4,1
1,3,5,2,1
1,3,5,4,1
1,3,5,2,4,1

C# 代码将更有帮助。谢谢。

Answer 1

看起来好像您想要输入集的幂集的笛卡尔积，但您不感兴趣的皱纹包括空集，它正式地是任何集的幂集的成员。我强调了两个术语，对 SO 的搜索将为这些操作生成算法，可能还有 C# 代码。

Answer 2

像这样的东西：（一组不包含重复项）

def permutate(set_to_perm, perm):
    Boolean used; 

    for elemen_set_  in set_to_perm:
        used = false

        for element_perm in perm
             if element_set_ == element_perm:
                 used = true;
                 break;
        if used false:
           if lengh(set_to_perm) < lenght(perm)
               permutate(set_to_perm, append element_set_ to perm)
           else:
               print per

take input from user;
set_to_perm = make a set from user input;
permutate(set_to_perm,[]):

Answer 3

您可以使用递归算法枚举所需的所有集合：

 current_set = { }

 enumerate (list_of_sets):
    if (list_of_sets is empty):
       REPORT current_set
    f = list_of_sets.front()
    r = list_of_sets.tail() /* all sets except f */
    n = f.size()
    for (i = 0 .. n - 1):
       current_set.insert(f[i])
       rec (f, i + 1, r)
       current_set.remove(f[i])

 rec (set, index, remaining_sets):
    if (index == set.size()):
       enumerate(remaining_sets)
    else:
       current_set.insert(f[index])
       rec(set, index + 1, remaining_sets)
       current_set.remove(f[index])
       rec(set, index + 1, remaining_sets)

Answer 4

由 F#

let rec comb n l =
  match n, l with
  | 0, _  -> [[]]
  | _, [] -> []
  | n, x::xs -> List.map (fun l -> x ::l) (comb (n - 1) xs) @ (comb n xs)

let powersets xs = seq {
    for i = 1 to List.length xs do
      for x in comb i xs -> x
  }

let rec powerset_out xs (acc:int list list) =
  if List.isEmpty xs then
    System.String.Join(",", seq { for el in acc do yield! el })
    |> printfn "%s"
  else
    let x::xs = xs
    for el in powersets x do
      powerset_out xs (acc @ [el])

执行示例：

> powerset_out [[1;3;5];[2;4];[1]] [];;
1,2,1
1,4,1
1,2,4,1
3,2,1
3,4,1
3,2,4,1
5,2,1
5,4,1
5,2,4,1
1,3,2,1
1,3,4,1
1,3,2,4,1
1,5,2,1
1,5,4,1
1,5,2,4,1
3,5,2,1
3,5,4,1
3,5,2,4,1
1,3,5,2,1
1,3,5,4,1
1,3,5,2,4,1