4

それぞれが異なる数の要素を持つ配列の数が与えられxた場合、各配列から1つのアイテムを選択するすべての組み合わせをどのように繰り返すことができますか？

例：

[   ]   [   ]   [   ]
 foo     cat      1
 bar     dog      2
 baz              3
                  4

戻り値

[foo]   [cat]   [ 1 ]
[foo]   [cat]   [ 2 ]
  ...
[baz]   [dog]   [ 4 ]

私はこれをPerlでやっています、ところで。

4

5 に答える 5

21

私のSet::CrossProductモジュールはまさにあなたが望むことをします。セット内の要素の順序である順列を実際に探しているわけではないことに注意してください。さまざまなセットの要素の組み合わせである外積を探しています。

私のモジュールはイテレータを提供するので、すべてをメモリ内に作成するわけではありません。必要な場合にのみ、新しいタプルを作成します。

use Set::Crossproduct;

my $iterator = Set::CrossProduct->new(
    [
        [qw( foo bar baz )],
        [qw( cat dog     )],
        [qw( 1 2 3 4     )],
    ]
    );

while( my $tuple = $iterator->get ) {
    say join ' ', $tuple->@*;
    }
于 2009-08-10T18:08:23.343 に答える
2

任意の数のリストに対する単純な再帰的ソリューション:

sub permute {
  my ($first_list, @remain) = @_;

  unless (defined($first_list)) {
    return []; # only possibility is the null set
  }

  my @accum;
  for my $elem (@$first_list) {
    push @accum, (map { [$elem, @$_] } permute(@remain));
  }

  return @accum;
}

任意の数のリストに対するそれほど単純ではない非再帰的なソリューション:

sub make_generator {
  my @lists = reverse @_;

  my @state = map { 0 } @lists;

  return sub {
    my $i = 0;

    return undef unless defined $state[0];

    while ($i < @lists) {
      $state[$i]++;
      last if $state[$i] < scalar @{$lists[$i]};
      $state[$i] = 0;
      $i++;
    }

    if ($i >= @state) {
      ## Sabotage things so we don't produce any more values
      $state[0] = undef;
      return undef;
    }

    my @out;
    for (0..$#state) {
      push @out, $lists[$_][$state[$_]];
    }

    return [reverse @out];
  };
}

my $gen = make_generator([qw/foo bar baz/], [qw/cat dog/], [1..4]);
while ($_ = $gen->()) {
  print join(", ", @$_), "\n";
}
于 2009-08-10T17:11:49.857 に答える
1

デカルト積を実行するための再帰的でより流暢な Perl の例 (解説とドキュメント付き) は、http://www.perlmonks.org/? node_id=7366 にあります。

例：

sub cartesian {
    my @C = map { [ $_ ] } @{ shift @_ };

    foreach (@_) {
        my @A = @$_;

        @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A;
    }

    return @C;
}
于 2009-08-10T18:31:43.203 に答える
-1

私が最初に思いついた方法が 1 つあります。これは、2 つの for ループを使用し、再帰を使用しません。

  1. 順列の総数を見つける
  2. 0 から total_permutations-1 までループ
  3. ループ インデックス モジュラスを配列内の要素の数にすることで、すべての順列を取得できることに注意してください。

例：

A[3]、B[2]、C[3]、

for (index = 0..totalpermutations) {
    print A[index % 3];
    print B[(index / 3) % 2];
    print C[(index / 6) % 3];
}

もちろん、for ループを [ABC ...] のループに置き換えることができ、小さな部分をメモすることができます。もちろん、再帰の方がきれいですが、再帰がスタック サイズによって厳しく制限されている言語では、これが役立つ場合があります。

于 2009-08-10T17:58:58.077 に答える