获得可能的阵列组合

Question

所以,

问题

从SQL我得到一个带字符串的数组(平面数组) - 让它成为

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

现在,我希望得到这个数组的对和三元组的可能组合(并且,通常情况下,4个元素的组合e tc).更具体一点:我的意思是数学意义上的组合(没有重复),即那些计数等于的组合

- 对于上面的数组,对于对和三元组都是10.

我的方法

我从映射可能的值开始 可能的数组选定项目.我目前的解决方案是指出一个元素被选为"1",否则为"0".对于上面的示例,将是:

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]

我需要做的就是以某种方式产生所需的位集.这是我在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. 在字符串中转到"01"的最右侧位置.将其切换为"10",然后将所有比找到"01"位置更粗的零 - 向左移动.例如,01110:"01"的最右侧位置为0,因此首先我们将此"01"切换为"10".字符串现在是10110.现在,转到右边的部分(它没有10部分,所以它从0 + 2 = 2-nd符号开始),并将所有零移动到左边, 110即将是011.结果,我们有10+ 011= 10111作为下一个关联01110.

我在这里发现了类似的问题- 但OP需要组合重复,而我希望它们没有重复.

这个问题

我的问题是关于两点:

• 对于我的解决方案,可能还有另一种方法可以产生更高效的下一位设置吗？
• 可能有更简单的解决方案吗？这似乎是标准问题.

Answer 1

很抱歉没有提供 PHP 解决方案，因为我已经很长时间没有使用 PHP 编程了，但是让我向您展示一个快速的 Scala 解决方案。也许它会给你带来启发：

val array = Vector("foo", "bar", "baz", "bee", "feo")
for (i <- 0 until array.size; 
     j <- i + 1 until array.size; 
     k <- j + 1 until array.size)      
    yield (array(i), array(j), array(k))

结果：

Vector((foo,bar,baz), (foo,bar,bee), (foo,bar,feo), (foo,baz,bee), (foo,baz,feo), (foo,bee,feo), (bar,baz,bee), (bar,baz,feo), (bar,bee,feo), (baz,bee,feo))

用于生成 k 组合的通用代码：

def combinations(array: Vector[String], k: Int, start: Int = 0): Iterable[List[String]] = { 
  if (k == 1 || start == array.length) 
    for (i <- start until array.length) yield List(array(i))
  else 
    for (i <- start until array.length; c <- combinations(array, k - 1, i + 1)) yield array(i) :: c 
}

结果：

scala> combinations(Vector("a", "b", "c", "d", "e"), 1)
res8: Iterable[List[String]] = Vector(List(a), List(b), List(c), List(d), List(e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 2)
res9: Iterable[List[String]] = Vector(List(a, b), List(a, c), List(a, d), List(a, e), List(b, c), List(b, d), List(b, e), List(c, d), List(c, e), List(d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 3)
res10: Iterable[List[String]] = Vector(List(a, b, c), List(a, b, d), List(a, b, e), List(a, c, d), List(a, c, e), List(a, d, e), List(b, c, d), List(b, c, e), List(b, d, e), List(c, d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 4)
res11: Iterable[List[String]] = Vector(List(a, b, c, d), List(a, b, c, e), List(a, b, d, e), List(a, c, d, e), List(b, c, d, e))

scala> combinations(Vector("a", "b", "c", "d", "e"), 5)
res12: Iterable[List[String]] = Vector(List(a, b, c, d, e))

当然，真正的 Scala 代码在接受的元素类型和集合类型方面应该更加通用，但我只是想展示基本思想，而不是最漂亮的 Scala 代码。