获取可能的排列组合， [英] Get possible array combinations

问题描述

因此，

问题

从SQL我收到带有字符串（平面数组）的阵列 - 让它成为

From SQL I'm getting an array with strings (flat array) - let it be

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

现在，我想这个数组对和三胞胎的可能组合（并且，在通常情况下，4个元件E TC组合）。更具体地讲：我的意思是组合在数学意义上（没有重复），即那些，这算等于

Now, I want to get possible combinations of pairs and triplets of this array (and, in common case, combinations of 4 elements e t.c.). To be more specific: I mean combinations in math sense (without duplicates), i.e. those, which count is equal to

- 所以对于阵列上方，这将是10两对三胞胎。

-so for array above that will be 10 for both pairs and triplets.

我的做法

我从测绘的可能值开始为可能的阵列选定的项目。我的当前的解决方案是，如果一个元件被选择为1，和0，否则为指向。对于上面的示例，这将是：

I've started from mapping possible values for to possible array selected items. My current solution is to point if an element is selected as "1", and "0" otherwise. For sample above that will be:

foo bar baz bee feo
 0   0   1   1   1   -> [baz, bee, feo]
 0   1   0   1   1   -> [bar, bee, feo]
 0   1   1   0   1   -> [bar, baz, feo]
 0   1   1   1   0   -> [bar, baz, bee]
 1   0   0   1   1   -> [foo, bee, feo]
 1   0   1   0   1   -> [foo, baz, feo]
 1   0   1   1   0   -> [foo, baz, bee]
 1   1   0   0   1   -> [foo, baz, feo]
 1   1   0   1   0   -> [foo, bar, bee]
 1   1   1   0   0   -> [foo, bar, baz]

和所有我需要做的就是以某种方式产生所需的位置。这是我的code在PHP中：

And all I need to do is somehow produce desired bit set. Here's my code in 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;
}

-I've选择来存储我的位作为一个普通的字符串。我的算法产生下一个关联是：

-I've chosen to store my bits as a normal string. My algorithm for producing next association is:

1. 尝试寻找01。如果没有找到，那么它的11..100..0情况下，（所以它的最大的，没有更多可以找到）。如果找到了，去第二步
2. 到最右边的的01的字符串的位置。切换到10，然后将是点对点的比找到了01的位置全部为零 - 向左。 例如， 01110 ：01的最合适的位置是0，所以我们首先关掉这个01至10。字符串现在门槛是 10110 。现在，转到右边部分（这是不 10 的一部分，所以它从0 + 2 = 2-ND符​​号开始），并将所有零到左，即 110 将 011 。作为结果，我们有 10 + 011 = 10111 作为明年联想 01110 。

1. Try to find "01". If not found, then it's 11..100..0 case (so it's maximum, no more could be found). If found, go to second step
2. Go to most right position of "01" in string. Switch it to "10" and then move all zeros that are righter than found "01" position - to left. For example, 01110: the most right position of "01" is 0, so first we switch this "01" to "10". String now sill be 10110. Now, go to right part (it's without 10 part, so it starts from 0+2=2-nd symbol), and move all zeros to left, i.e. 110 will be 011. As result, we have 10+011=10111 as next association for 01110.

我发现类似的问题<一href="http://stackoverflow.com/questions/12293870/algorithm-to-get-all-possible-string-combinations-from-array-up-to-certain-lengt?rq=1">here - 但OP想要组合，带重复的，而我希望他们不重复

I've found similar problem here - but there OP wants combinations with duplicates, while I want them without duplicated.

问题

我的问题是关于两点：

• 对于我的解决方案，可能还有另一种方式来产生下一个位为更有效？
• 在可能有这种更简单的解决方案？这似乎是标准的问题。

推荐答案

下面是一个递归的解决方案：

Here is a recursive solution:

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的所有组合（ $计数）的元素出 N （ $ arr_size ）你一定要，最高从零开始的索引的所有可能的选择我，找到 K-1 元素出的剩余我比元素我。

The recursion is based on the fact that to get all combinations of k ($count) elements out of n ($arr_size) you must, for all possible choices of the highest zero-based index i, find all "subcombinations" of k-1 elements out of the remaining i elements with index lower than i.

该阵列是不是当它传递给递归调用，以利用PHP的懒惰复制机制 array_slice D。这种方式没有真正进行复制操作，因为该数组不会被修改。

The array is not array_sliced when it's passed to the recursive calls in order to take advantage of PHP's "lazy copy" mechanism. This way no real copying takes place, since the array is not modified.

节约数组索引是很好的调试，但它不是必需的。出人意料的是，简单地删除 $ I =＆GT; 配件和更换阵列 + 与 array_merge 造成相当大的经济放缓。为了达到一个稍微好一点的速度比原来的版本，你必须要做到这一点：

Conserving array indices is nice for debugging purposes, but it's not necessary. Surprisingly, simply removing the $i => parts and replacing the array + with an array_merge causes a considerable slowdown. To attain a slightly better speed than the original version, you have to do this:

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;
}

---

关于你问题的第一部分，你应该避免计算相同数量超过一次，你应该函数调用减少。例如，像这样的：

---

Regarding the first part of your question, you should avoid calculating the same quantity more than once, and you should minimize function calls. E.g., like this:

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;
}

这是很难做的，你的code更深层次的变化，而不把它里面出来。这不是太糟糕了，虽然，因为在我的测试中其速度大约是一半对我的递归解决方案（即，时间长约双）

It's hard to do deeper changes to your code without turning it inside out. It's not too bad though, since in my tests its speed is approximately half the one of my recursive solution (i.e., times are ca. double)

这篇关于获取可能的排列组合，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！