1

次のシーケンスを生成したい:

set S = {1,2,3}
op = {{1,2},{1,3},{2,3}}

set S = {1,2,3,4}
op = {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

set S = {1,2,3,4,5}
op = {{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}

一般に、n 個の数字のセットが与えられた場合、(n-1) 個の数字のすべての可能なサブセットを、それらがアルファベット順 (順番にある数字) であるという制約の下で見つけなければなりません。

特定の問題を解決するためのアルゴリズムまたはアプローチはありますか? 再帰を使用して小さなサブセットを生成できることはわかっています。

4

5 に答える 5

2

について考える

  • セット1..Nを生成する方法
  • 各セットから削除する数nを識別する方法（n：N .. 1）

1..Nからセットを生成/印刷するには

print "{"
for i=1 to N
  if (i > 1) print ","
  print i
end
print "}"

Nから1までnを選択するループを作成する方法

for j=N to 1 
  ...
end

その最後のループを上記のループのラッパーとして使用します。上記のループでは、現在選択されている数値jがiと等しいかどうかをテストし、その場合は出力しません。

楽しみのために、最適化されたふりをしないPerl実装:-)

$N = 5;

sub rec {
  my($j,$i,@a) = @_;
  if ($j > 0) {
    while (++$i <= $N) { push(@a,$i) if ($i != $j); }
    print('{' . join(',', @a) . "}\n");
    &rec($j-1);
  }
}

&rec($N);

またはこれ、（多分）より従来型

for ($i=$N ; $i>0 ; $i--) {
  @a = ();
  for (1..$N) { push(@a,$_) if ($i != $_); }
  print('{' . join(',', @a) . "}\n");
}
于 2013-02-23T12:22:16.767 に答える
1

Haskellでは、これを行うことができます:

import Data.List

combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

subsets set =  combinations (length set - 1) (sort set)


ハスケル、簡単に：

_                                   =>    anyting
[]                                  =>    empty list
a = 1; as = [2,3]                   =>    a:as = [1,2,3]
[a:b | a <- [1], b <- [[2],[3]]]    =>    [[1,2],[1,3]]
tails [1,2,3]                       =>    [[1,2,3],[2,3],[3],[]]


たとえば、「組み合わせ 2 [1,2,3]」:

tails xs = [[1,2,3],[2,3],[3],[]]

[1,2,3]   =>   y = 1; ys = [[2],[3]]    =>    [1,2],[1,3]
[2,3]     =>   y = 2; ys = [[3]]        =>    [2,3]
[3]       =>   y = 3; ys = NULL         =>    []

Result [[1,2],[1,3],[2,3]]
于 2013-02-23T14:58:04.210 に答える