1

ユーザーが入力した多数の (不明な) セットから、各セットから少なくとも 1 つおよび最大ですべての要素を選択した結果として生じるすべての可能な組み合わせをリストしたいと考えています。要素は複数のセットに含まれる場合がありますが、複数回リストすることは問題ではありません。

例:- ユーザーが次のように 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# コードはさらに役に立ちます。ありがとう。

4

4 に答える 4

1

入力セットの累乗セットのデカルト積が必要なように見えますが、形式的には任意のセットの累乗セットのメンバーである空のセットを含めることに関心がないというしわがあります。私は 2 つの用語を強調しました。SO を検索すると、これらの操作のアルゴリズム (おそらく C# コードも) が生成されます。

于 2012-05-29T10:49:10.490 に答える
0

再帰アルゴリズムを使用して、必要なすべてのセットを列挙できます。

 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)
于 2012-05-28T17:25:09.840 に答える
0

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
于 2012-05-28T22:58:45.840 に答える
0

このようなもの：（セットには重複が含まれていません）

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,[]):
于 2012-05-28T16:47:19.257 に答える