4

値の配列を含む次の配列があります。

$array = array(
    array('1', '2'),
    array('a', 'b', 'c'),
    array('x', 'y'),
);

任意の数の配列が存在する可能性があり、配列には任意の数の値を含めることができます。現在、各配列から 1 つの値が取得されるすべての組み合わせを生成するコードがあります。例えば：

1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy

ただし、実際に必要なのは、各列に値が 1 つだけある組み合わせのみです。1ax は、1、a、x の 3 つの値すべてが最初の列にあるため、適切ではありません。1by は、b と y が 2 番目の列にあるため、適切ではありません。したがって、上記の例から、これらの組み合わせのみが有効になります。

1cy, 2cx

私は当初、すべての組み合わせを生成し、競合のあるものを除外することを計画していましたが、これは単純化しすぎた例であるため、拡張できません。実際のアプリケーションでは、潜在的に何百万もの組み合わせ (競合するものを含む) が存在する状況が発生します。 ）。

誰でもこれを解決するためのより良い方法を手伝ってもらえますか? 私は PHP で作業していますが、ロジックを明確に示すコード サンプルは役に立ちます。

前もって感謝します。

アップデート：

ベンチマークを取得するために、より大きなデータセットに対して機能するソリューションをテストしました。これまでの結果は次のとおりです。

$array = array(
    array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'),
    array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
    array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'),
    array('1', '2', '3', '1', '2', '3', '1', '2', '3'),
    array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
    array('x', 'y', 'z'),
);

Josh Davis 2番目のソリューション:

Combinations:      249480
Time:              0.3180251121521 secs
Memory Usage:      22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb

ジョシュ・デイビス：

Combinations:      249480
Time:              1.1172790527344 secs
Memory Usage:      22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb

トム・ヘイ：

Combinations:      249480
Time:              5.7098741531372 secs
Memory Usage:      39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
4

9 に答える 9

4

面白い問題！これは思ったよりも複雑であることが判明しましたが、うまくいくようです。

基本的な戦略は、最初に配列を最小から最大に並べることです (正しい順序で答えを出力できるように、配列の順序を追跡します)。

この並べ替えられた入力リストの配列に、インデックスの配列の形式で回答を保持します。

リストがソートされたので、最初の正解を array(0,1,2,...,n); として保存できます。

次に、最初のスロット (上記の 0) 内のすべての値を、その応答配列内の他の値 (そのスロットに対して大きすぎないすべての値) と交換することによって試す関数に再帰します。サイズでソートされているので、右のスロットに対して大きすぎることを心配することなく、スワップするときに任意の値を右に移動できます。

各有効なスロットを出力すると、すべての並べ替えを元に戻すというクレイジーな間接性があります。

これが混乱しているように見える場合は申し訳ありません。私はそれをきれいにするのに多くの時間を費やしませんでした。

<?php
# $lists is an array of arrays
function noconfcombos($lists) {
    $lengths = array();
    foreach($lists as $list) {
        $lengths[] = count($list);
    }

    # find one solution (and make sure there is one)
    $answer = array();
    $sorted_lengths = $lengths;
    asort($sorted_lengths);
    $answer_order_lists = array();
    $answer_order_lengths = array();
    $output_order = array();
    $min = 1;
    $max_list_length = 0;
    foreach($sorted_lengths as $lists_key => $list_max) {
        if($list_max < $min) {
            # no possible combos
            return array();
        }
        $answer[] = $min - 1; # min-1 is lowest possible value (handing out colums starting with smallest rows)
        $output_order[$lists_key] = $min - 1; # min-1 is which slot in $answers corresponds to this list
        $answer_order_lists[] = $lists[$lists_key];
        $answer_order_lengths[] = $lengths[$lists_key];
        ++$min;
    }
    ksort($output_order);
    $number_of_lists = count($lists);
    $max_list_length = end($sorted_lengths);
    if($max_list_length > $number_of_lists) {
       for($i = $number_of_lists; $i < $max_list_length; ++$i) {
          $answer[] = $i;
       }
       $stop_at = $number_of_lists;
    } else {
       $stop_at = $number_of_lists - 1;
    }

    # now $answer is valid (it has the keys into the arrays in $list for the
    # answer), and we can find the others by swapping around the values in
    # $answer.

    $ret = array();
    $ret[] = noconfcombos_convert($answer, $answer_order_lists, $output_order);
    noconfcombos_recurse($ret, $max_list_length, $stop_at, $answer_order_lengths, $answer_order_lists, $output_order, $answer, 0);

    return $ret;
}

# try swapping in different indexes into position $index, from the positions
# higher, then recurse
function noconfcombos_recurse(&$ret, $max_list_length, $stop_at, &$lengths, &$lists, &$output_order, $answer, $index) {
    if($index < $stop_at) {
        noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
    }
    for($other = $index + 1; $other < $max_list_length; ++$other) {
        if($answer[$other] < $lengths[$index]) { # && $answer[$index] < $lengths[$other]) {
            $tmp = $answer[$index];
            $answer[$index] = $answer[$other];
            $answer[$other] = $tmp;
            $ret[] = noconfcombos_convert($answer, $lists, $output_order);
            if($index < $stop_at) {
                noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1);
            }
        }
    }
}


function noconfcombos_convert(&$indexes, &$lists, &$order) {
    $ret = '';
    foreach($order as $i) {
        $ret .= $lists[$i][$indexes[$i]];
    }
    return $ret;
}

function noconfcombos_test() {
    $a = array('1', '2', '3', '4');
    $b = array('a', 'b', 'c', 'd', 'e');
    $c = array('x', 'y', 'z');
    $all = array($a, $b, $c);
    print_r(noconfcombos($all));
}

noconfcombos_test();
于 2009-09-04T11:11:51.113 に答える
3

これはうまくいくと思います。再帰を使用して、ツリーのような構造をたどっています。分岐ごとに、どの列が既に使用されているかを追跡します。総当たり的なアプローチであるため、おそらく遅いです。

<?php 

$array = array(
    array('1', '2'),
    array('a', 'b', 'c'),
    array('x', 'y'),
);


function f($array, & $result, $colsToIgnore = array(), $currentPath = array()) {
    $row = array_shift($array);
    $length = count($row);
    $isMoreRows = !! count($array);

    for ($col = 0; $col < $length; $col++) {
        //check whether column has already been used
        if (in_array($col, $colsToIgnore)) {
            continue;   
        }

        $item = $row[$col];

        $tmpPath = $currentPath;
        $tmpPath[] = $item;

        if ($isMoreRows) {
            $tmpIgnoreCols = $colsToIgnore;
            $tmpIgnoreCols[] = $col;
            f($array, $result, $tmpIgnoreCols, $tmpPath);
        } else {
            $result[] = implode('', $tmpPath);
        }

    }
}


$result = array();
f($array, $result);
print_r($result);
于 2009-09-04T10:52:25.960 に答える
3

これは、自己生成コードとブルート フォースが、シンプルさとパフォーマンスの点でほとんどのアルゴリズムに勝るケースの 1 つです。以前の回答では、実際にやりたいことは次のとおりですが、多くの再帰、配列操作、および計算を見てきました。

foreach ($array[0] as $k0 => $v0)
{
    foreach ($array[1] as $k1 => $v1)
    {
        if ($k1 == $k0)
        {
            continue;
        }
        foreach ($array[2] as $k2 => $v2)
        {
            if ($k2 == $k1 || $k2 == $k0)
            {
                continue;
            }
            $result[] = $v0.$v1.$v2;
        }
    }
}

もちろん、 にいくつの配列があるかを知らなければ、これを書くことはできません$array。そこで、生成されたコードが役に立ちます。

$array = array(
    array('1', '2'),
    array('a', 'b', 'c'),
    array('x', 'y')
);
$result = array();

$php = '';
foreach ($array as $i => $arr)
{
    $php .= 'foreach ($array[' . $i . '] as $k' . $i . ' => $v' . $i . '){';

    if ($i > 0)
    {
        $sep  = 'if (';
        $j    = $i - 1;
        do
        {
            $php .= $sep . '$k' . $i . ' == $k' . $j;
            $sep  = ' || ';
        }
        while (--$j >= 0);

        $php .= ') { continue; } ';
    }
}

$php .= '$result[] = $v' . implode('.$v', array_keys($array)) . ';' . str_repeat('}', count($array));

eval($php);
print_r($result);

このルーチンは$array、例のように、ゼロベースの数値インデックス付き配列であると想定していることに注意してください。上記のコードを生成し、任意の数の配列に合わせて調整します。

アップデート

これが代替アルゴリズムです。それはまだ自己生成ですが、ブルートフォースは少なくなります。ネストされたループはまだありますが、各ループは、現在外側のループで使用されているキーがこのループの配列から削除された配列のコピーで機能します。たとえば、値が (a,b,c) である必要があるが、外側のループがインデックス 0 と 2 を使用している場合、"a" (インデックス 0) と "c" (インデックス 2) を削除すると、 "b"。つまり、ループは可能な組み合わせでのみ機能し、if条件はもう必要ありません。

さらに、この部分は前のアルゴリズムにも適用できます。使用されたインデックスが現在の配列に存在することを保証するために、値の配列を最小から最大の順に処理します。欠点は、組み合わせが同じ順序で生成されないことです。同じ組み合わせが生成されますが、同じ順序ではありません。コードは次のようになります。

$a0 = $array[0];
foreach ($a0 as $k0 => $v0)
{
    $a2 = $array[2];
    unset($a2[$k0]);
    foreach ($a2 as $k2 => $v2)
    {
        $a1 = $array[1];
        unset($a1[$k0], $a1[$k2]);
        foreach ($a1 as $k1 => $v1)
        {
            $result[] = "$v0$v1$v2";
        }
    }
}

上記のルーチンは、すべてのループの開始時に値のコピーを設定し、外側のループで使用される値を削除します。このプロセスを改善するには、値のコピーを最初に1 回だけ設定し、キーが使用されたときに (各ループの最初に) キーを削除し、解放されたときに (各ループの最後に) 元に戻します。 . ルーチンは次のようになります。

list($a0,$a1,$a2) = $array;
foreach ($a0 as $k0 => $v0)
{
    unset($a1[$k0], $a2[$k0]);
    foreach ($a2 as $k2 => $v2)
    {
        unset($a1[$k2]);
        foreach ($a1 as $k1 => $v1)
        {
            $result[] = "$v0$v1$v2";
        }
        $a1[$k2] = $array[1][$k2];
    }
    $a1[$k0] = $array[1][$k0];
    $a2[$k0] = $array[2][$k0];
}

上記のソースを生成する実際のコードは次のとおりです。

$keys = array_map('count', $array);
arsort($keys);

$inner_keys = array();
foreach ($keys as $k => $cnt)
{
    $keys[$k] = $inner_keys;
    $inner_keys[] = $k;
}

$result = array();

$php = 'list($a' . implode(',$a', array_keys($array)) . ')=$array;';
foreach (array_reverse($keys, true) as $i => $inner_keys)
{
    $php .= 'foreach ($a' . $i . ' as $k' . $i . ' => $v' . $i . '){';

    if ($inner_keys)
    {
        $php .= 'unset($a' . implode('[$k' . $i . '],$a', $inner_keys) . '[$k' . $i . ']);';
    }
}

$php .= '$result[] = "$v' . implode('$v', array_keys($array)) . '";';

foreach ($keys as $i => $inner_keys)
{
    foreach ($inner_keys as $j)
    {
        $php .= '$a' . $j . '[$k' . $i . ']=$array[' . $j . '][$k' . $i . "];\n";
    }
    $php .= '}';
}
eval($php);
于 2009-09-04T13:32:55.423 に答える
1

別のオプション：

    $arr = array(
        array('1', '2'),
        array('a', 'b', 'c'),
        array('x', 'y'),
    );
    //-----
    //assuming $arr consists of non empty sub-arrays
    function array_combinations($arr){ 
        $max = 1;
        for ($i = 0; $i < count($arr); $i ++){
            $max *= count($arr[$i]); 
        }
        $matrix = array();
        for ($i = 0; $i < $max; $i ++){
            $matrix = array(); 
        }
        $c_rep = 1;
        for ($i = count($arr) - 1; $i >= 0; $i --){
            $c_rep *= ($i < count($arr) - 1)//last sub-array 
                ? count($arr[$i + 1])
                : 1;
            $k = 0; 
            while ($k < $max){
                for ($t = 0; $t < count($arr[$i]); $t ++){
                    for ($j = 0; $j < $c_rep; $j ++){
                        $matrix[$i][$k ++] = $arr[$i][$t];
                    }
                }   
            }
        }
        return $matrix;
    }
    //-----
    $matrix = array_combinations($arr);
于 2012-09-11T00:38:25.770 に答える
1

これは、再帰を使用してリファクタリングし、任意の量の配列で機能させることができます。時間があれば自分も挑戦してみます。

ps。私はphpを知りません。例はDelphiで書かれています。

編集:任意の # 配列を使用した再帰的ソリューション

type
  TSingleArray = array of string;
  TMasterArray = array of TSingleArray;
var
  solutions: array of integer; // Q&D container to hold currently used indexes of SingleArrays


procedure WriteSolution(const masterArray: TMasterArray);
var
  I: Integer;
  indexes: string;
  solution: string;
begin
  for I := 0 to High(solutions) do
  begin
    indexes := indexes + IntToStr(solutions[I]) + ' ';
    solution := solution + masterArray[I][solutions[I]];
  end;
  Writeln('Solution: ' + solution + ' Using indexes: ' + indexes);
end;

procedure FindSolution(const masterArray: TMasterArray; const singleArrayIndex: Integer; var bits: Integer);
var
  I: Integer;
begin
  for I := 0 to High(masterArray[singleArrayIndex]) do
  begin
    //***** Use bit manipulation to check if current index is already in use
    if bits and (1 shl I)  = (1 shl I ) then continue;
    solutions[singleArrayIndex] := I;
    Inc(bits, 1 shl I);
    //***** If it is not the last array in our masterArray, continue by calling RecursArrays recursivly.
    if singleArrayIndex <> High(masterArray) then FindSolution(masterArray, Succ(singleArrayIndex), bits)
    else WriteSolution(masterArray);
    Dec(bits, 1 shl I);
  end;
end;

//***************
// Initialization
//***************
var
  I, J: Integer;
  bits: Integer;
  singleArrayString: string;
  masterArray: TMasterArray;
begin
  I := 10;
  SetLength(masterArray, I);
  for I := 0 to High(masterArray) do
  begin
    SetLength(masterArray[I], High(masterArray) + Succ(I));
    singleArrayString := EmptyStr;
    for J := 0 to High(masterArray[I]) do
    begin
      masterArray[I][J] := IntToStr(J);
      singleArrayString := singleArrayString + masterArray[I][J];
    end;
    WriteLn(singleArrayString)
  end;
  ReadLn;

  //****** Start solving the problem using recursion
  bits := 0;
  SetLength(solutions, Succ(High(masterArray)));
  FindSolution(masterArray, 0, bits);    
end.
于 2009-09-04T10:23:59.447 に答える
1

別の角度から見てみましょう。結果行を構成するには、各列の値を選択する必要があります。各値は、異なるソース行から選択する必要があります。この問題は、「M から N を選択する」、またはより数学的にはCombinationとして知られています。

これは、結果行がソース行インデックスの配列に対応することを意味します。

このようなインデックス配列の構築を開始することで、可能なすべてのピッキングを構築できます (疑似コード)

function combinations( $source ) {
  if( count( $source ) == 0 ) return $source;
  $result=array();
  // build one row
  foreach( $source as $index=>$value ) {
    $newsource = array_splice( $source, $index, 1 );

    $reduced_combinations=combinations( $newsource  );
    foreach( $reduced_combinations as $reduced_combi ) {
      $newrow=array_unshift( $reduced_combi, $value );
      $result[]=$newrow;
    }

  }
  return $result;
}

function retrieve_indices( $indices, $arrays ) {
   $result=array();
   foreach( $indices as $column=>$index ) {
     $result[]=$arrays[$index][$column];
   }
   return $result;
}

$source_arrays = array(
  array( "1", "2", "3" ),
  array( "a", "b", "c" ),
  array( "x", "y", "z" )
);

$index_combinations = combinations( range(0,2) );
$result=array();
foreach( $index_combinations as $combination ) {
  $result[]=retrieve_indices( $combination, $source_arrays );
}
于 2009-09-04T12:17:52.510 に答える
1

おそらく最もエレガントな方法ではありませんが、うまくいきます（javascript）

var result = [];

for(i=0;i<arr1.length;i++)
{
  for(j=0;j<arr2.length;j++)
  {
    if(j==i)
      continue;
    else
    {
      for(k=0;k<arr3.length;k++)
      {
        if(k==i||k==j)
          continue;
        else
        {
          result.push(arr1[i]+arr2[j]+arr3[k]);
        }
      }
    }
  }
}
于 2009-09-04T10:02:21.100 に答える
0

あなたの問題は、行列式の行列式を見つけることと似ています。imhoの最善の方法は、小さい配列に「0」などの記号を入力することです。これにより、例では、すべての値が同じ数になります。

$array = array(
    array('1', '2', '0'),
    array('a', 'b', 'c'),
    array('x', 'y', '0'),
);

次に、最初の配列値のそれぞれをループし、配列のインデックスを1ずつインクリメントして、次の配列と次の列を確認します（最初のループでは、「1」になり、インデックスは0インクリメントされます-1、次に$ array 1 -'b'など） '0'に達した場合は中断し、右の境界に達した場合は最初のインデックスを0にリセットします。次に、デクリメントを使用して同じことを行うと、すべての組み合わせが得られます。おそらく不明です。リンクした画像を確認してください

于 2009-09-04T10:49:56.667 に答える
0

これを試して ：

function algorithmToCalculateCombinations($n, $elems) {
        if ($n > 0) {
            $tmp_set = array();
            $res = algorithmToCalculateCombinations($n - 1, $elems);
            foreach ($res as $ce) {
                foreach ($elems as $e) {
                    array_push($tmp_set, $ce . $e);
                }
            }
            return $tmp_set;
        } else {
            return array('');
        }
    }

$Elemen = array(range(0,9),range('a','z'));
$Length = 3;
$combinations = algorithmToCalculateCombinations($Length, $Elemen);
于 2015-05-04T13:42:56.210 に答える