6

それで、

問題

SQL から、文字列を含む配列 (フラット配列) を取得しています。

$rgData = ['foo', 'bar', 'baz', 'bee', 'feo'];

ここで、この配列のペアとトリプレットの可能な組み合わせ (および、一般的なケースでは、4 つの要素などの組み合わせ) を取得したいと考えています。より具体的に言うと、数学的な意味での組み合わせ（重複なし）、つまり、カウントが等しい組み合わせを意味します

ここに画像の説明を入力

-上記の配列の場合、ペアとトリプレットの両方で10になります。

私のアプローチ

ここに画像の説明を入力可能な値を可能な配列選択項目にマッピングすることから始めました。私の現在の解決策は、要素が「1」として選択されている場合はポイントし、それ以外の場合は「0」をポイントすることです。上記のサンプルでは、​​次のようになります。

フー・バー・バズ・ビー・フェオ
 0 0 1 1 1 -> [バズ、ビー、フェオ]
 0 1 0 1 1 -> [バー、ビー、フェオ]
 0 1 1 0 1 -> [バー、バズ、フェオ]
 0 1 1 1 0 -> [バー、バズ、ビー]
 1 0 0 1 1 -> [フー、ビー、フェオ]
 1 0 1 0 1 -> [フー、バズ、フェオ]
 1 0 1 1 0 -> [フー、バズ、ビー]
 1 1 0 0 1 -> [フー、バズ、フェオ]
 1 1 0 1 0 -> [フー、バー、ビー]
 1 1 1 0 0 -> [フー、バー、バズ]

そして、私がする必要があるのは、どうにかして目的のビットセットを生成することだけです。PHPでの私のコードは次のとおりです。

function nextAssoc($sAssoc)
{
   if(false !== ($iPos = strrpos($sAssoc, '01')))
   {
      $sAssoc[$iPos]   = '1';
      $sAssoc[$iPos+1] = '0';
      return substr($sAssoc, 0, $iPos+2).
             str_repeat('0', substr_count(substr($sAssoc, $iPos+2), '0')).
             str_repeat('1', substr_count(substr($sAssoc, $iPos+2), '1'));
   }
   return false;
}

function getAssoc(array $rgData, $iCount=2)
{
   if(count($rgData)<$iCount)
   {
      return null;
   }
   $sAssoc   = str_repeat('0', count($rgData)-$iCount).str_repeat('1', $iCount);
   $rgResult = [];
   do
   {
      $rgResult[]=array_intersect_key($rgData, array_filter(str_split($sAssoc)));
   }
   while($sAssoc=nextAssoc($sAssoc));
   return $rgResult;
}

-ビットを通常の文字列として保存することにしました。次の関連付けを生成するための私のアルゴリズムは次のとおりです。

  1. 「01」を探してみてください。見つからない場合は、11..100..0 のケースです (つまり、最大値であり、それ以上は見つかりませんでした)。見つかった場合は、2 番目のステップに進みます
  2. 文字列の "01" の一番右の位置に移動します。「10」に切り替えてから、見つかった「01」位置よりも右側にあるすべてのゼロを左に移動します。たとえば、01110「01」の一番右の位置は 0 なので、まずこの「01」を「10」に切り替えます。文字列は現在 sill です10110。次に、右側の部分 (10部分がないため、0+2 = 2 番目のシンボルから開始) に移動し、すべてのゼロを左に移動します。つまり、 110になります011。その結果、の次の関連付けとして10+ 011=が得られます。1011101110

ここで同様の問題が見つかりました-しかし、OPは重複した組み合わせを望んでいますが、重複していないものを望んでいます。

質問

私の質問は次の 2 点です。

  • 私の解決策では、次のビットセットをより効率的に生成する別の方法があるでしょうか?
  • これにはもっと簡単な解決策があるでしょうか？標準問題のようです。
4

3 に答える 3

1

再帰的な解決策は次のとおりです。

function subcombi($arr, $arr_size, $count)
{
   $combi_arr = array();
   if ($count > 1) {
      for ($i = $count - 1; $i < $arr_size; $i++) {
         $highest_index_elem_arr = array($i => $arr[$i]);
         foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) {
            $combi_arr[] = $subcombi_arr + $highest_index_elem_arr;
         }
      }
   } else {
      for ($i = $count - 1; $i < $arr_size; $i++) {
         $combi_arr[] = array($i => $arr[$i]);
      }
   }
   return $combi_arr;
}

function combinations($arr, $count)
{
   if ( !(0 <= $count && $count <= count($arr))) {
      return false;
   }
   return $count ? subcombi($arr, count($arr), $count) : array();
}    

$input_arr = array('foo', 'bar', 'baz', 'bee', 'feo');
$combi_arr = combinations($input_arr, 3);
var_export($combi_arr); echo ";\n";

OUTPUT:

array (
  0 => 
  array (
    0 => 'foo',
    1 => 'bar',
    2 => 'baz',
  ),
  1 => 
  array (
    0 => 'foo',
    1 => 'bar',
    3 => 'bee',
  ),
  2 => 
  array (
    0 => 'foo',
    2 => 'baz',
    3 => 'bee',
  ),
  3 => 
  array (
    1 => 'bar',
    2 => 'baz',
    3 => 'bee',
  ),
  4 => 
  array (
    0 => 'foo',
    1 => 'bar',
    4 => 'feo',
  ),
  5 => 
  array (
    0 => 'foo',
    2 => 'baz',
    4 => 'feo',
  ),
  6 => 
  array (
    1 => 'bar',
    2 => 'baz',
    4 => 'feo',
  ),
  7 => 
  array (
    0 => 'foo',
    3 => 'bee',
    4 => 'feo',
  ),
  8 => 
  array (
    1 => 'bar',
    3 => 'bee',
    4 => 'feo',
  ),
  9 => 
  array (
    2 => 'baz',
    3 => 'bee',
    4 => 'feo',
  ),
);

再帰は、k( $count) 要素のすべての組み合わせをn( ) から取得する$arr_sizeには、最高のゼロベースのインデックスのすべての可能な選択肢について、インデックスが小さい残りの要素から要素iのすべての「サブコンビネーション」を見つけなければならないという事実に基づいています。よりも。k-1ii

array_slicePHP の「レイジー コピー」メカニズムを利用するために、配列が再帰呼び出しに渡されると、配列は d になりません。この方法では、配列が変更されないため、実際のコピーは行われません。

配列インデックスを保存することは、デバッグ目的には便利ですが、必須ではありません。驚くべきことに、$i =>パーツを取り外して配列+をに置き換えるだけでarray_merge、かなりの速度低下が発生します。元のバージョンよりもわずかに速度を上げるには、次のようにする必要があります。

function subcombi($arr, $arr_size, $count)
{
   $combi_arr = array();
   if ($count > 1) {
      for ($i = $count - 1; $i < $arr_size; $i++) {
         $highest_index_elem = $arr[$i];
         foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) {
            $subcombi_arr[] = $highest_index_elem;
            $combi_arr[] = $subcombi_arr;
         }
      }
   } else {
      for ($i = $count - 1; $i < $arr_size; $i++) {
         $combi_arr[] = array($arr[$i]);
      }
   }
   return $combi_arr;
}

質問の最初の部分については、同じ数量を複数回計算することは避け、関数呼び出しを最小限に抑える必要があります。たとえば、次のようにします。

function nextAssoc($sAssoc)
{
   if (false !== ($iPos = strrpos($sAssoc, '01')))
   {
      $sAssoc[$iPos]   = '1';
      $sAssoc[$iPos+1] = '0';
      $tailPos = $iPos+2;
      $n0 = substr_count($sAssoc, '0', $tailPos);
      $n1 = strlen($sAssoc) - $tailPos - $n0;
      return substr($sAssoc, 0, $tailPos).str_repeat('0', $n0)
                                         .str_repeat('1', $n1);
   }
   return false;
}

コードを裏返しにせずに、コードをさらに深く変更することは困難です。ただし、私のテストでは、その速度は再帰的なソリューションの約半分であるため、それほど悪くはありません (つまり、時間は約 2 倍になります)。

于 2013-10-24T21:39:21.150 に答える