动态组合算法

Question

我的代码有一个名为 INPUTS 的列表，其中包含动态数量的列表，我们称它们为 A、B、C、.. N。这些列表包含动态数量的事件，

我想用每个事件组合调用一个函数。用一个例子来说明：

INPUTS: A(0,1,2), B(0,1), C(0,1,2,3)

我需要为每个组合调用我的函数很多次（输入计数是动态的，在这个例子中它是三个参数，但它可以更多或更少）

function(A[0],B[0],C[0]) 
function(A[0],B[1],C[0]) 
function(A[0],B[0],C[1])
function(A[0],B[1],C[1])
function(A[0],B[0],C[2]) 
function(A[0],B[1],C[2])
function(A[0],B[0],C[3])
function(A[0],B[1],C[3])

function(A[1],B[0],C[0]) 
function(A[1],B[1],C[0]) 
function(A[1],B[0],C[1])
function(A[1],B[1],C[1])
function(A[1],B[0],C[2]) 
function(A[1],B[1],C[2])
function(A[1],B[0],C[3])
function(A[1],B[1],C[3])

function(A[2],B[0],C[0]) 
function(A[2],B[1],C[0]) 
function(A[2],B[0],C[1])
function(A[2],B[1],C[1])
function(A[2],B[0],C[2]) 
function(A[2],B[1],C[2])
function(A[2],B[0],C[3])
function(A[2],B[1],C[3])

这是我到目前为止所想到的： 到目前为止，我的方法是建立一个组合列表。元素组合本身就是输入数组 A、B 和 C 的“索引”列表。对于我们的示例：

我的列表 iCOMBINATIONS 包含以下 iCOMBO 列表

(0,0,0) 
(0,1,0) 
(0,0,1)
(0,1,1)
(0,0,2) 
(0,1,2)
(0,0,3)
(0,1,3)

(1,0,0) 
(1,1,0)  
(1,0,1) 
(1,1,1)
(1,0,2) 
(1,1,2)
(1,0,3) 
(1,1,3)

(2,0,0)
(2,1,0)  
(2,0,1) 
(2,1,1)
(2,0,2) 
(2,1,2)
(2,0,3) 
(2,1,3)

然后我会这样做：

foreach( iCOMBO in iCOMBINATIONS)
{
      foreach ( P in INPUTS )
      {
           COMBO.Clear()
           foreach ( i in iCOMBO )
           {
                 COMBO.Add( P[ iCOMBO[i] ] )
           }
           function( COMBO ) --- (instead of passing the events separately)
      }
}

但我需要找到一种方法来构建列表iCOMBINATIONS 用于任何给定数量的输入及其事件。有什么想法吗？

实际上还有比这更好的算法吗？ 任何可以帮助我的伪代码都会很棒。

C#（或 VB）

谢谢

Answer 1

您可以使用数组来保存每个列表的索引。例子：

List<List<int>> lists = new List<List<int>> {
  new List<int> { 0,1,2 },
  new List<int> { 0,1 },
  new List<int> { 0,1,2,3 }
};

int[] cnt = new int[lists.Count];
int index;
do {
  Console.WriteLine(String.Join(",", cnt.Select((c,i) => lists[i][c].ToString()).ToArray()));
  index = cnt.Length - 1;
  do {
    cnt[index] = (cnt[index] + 1) % lists[index].Count;
  } while(cnt[index--] == 0 && index != -1);
} while (index != -1 || cnt[0] != 0);

Answer 2

这就是排列问题。您可以看一下：

http://www. Interactive-sw.co.uk/iangblog/2004/09/16/permuterate

Answer 3

我前段时间遇到了类似的问题（生成组合），我使用了以下代码： http://www .merriampark.com/comb.htm。它是java，但我把它翻译成C#没有任何问题。

Answer 4

将A、B、C放入矩阵中！
M=[A,B,C]

recursive_caller(d,params):
    if d == len(M):
        function(params)
        return

    for i in M[d]:
        params[d]=i
        recursive_caller(d+1,params)

Answer 5

看来您真正想要的，本身既不是排列，也不是组合。您想要查看笛卡尔积（请参阅此处）的多个集合，其迭代可能涉及迭代各个集合的组合。

然而，这与组合问题不同，因为您正在寻找从每个集合中选择 1 个元素的方法。执行此操作的方法数量就是集合的大小。组合问题通常涉及选择k - 从一组n中选择许多东西 - 许多东西，其中k=1或n 是微不足道的。

此处。 （包括乔恩·斯基特的一首）。

如果您使用 .NET，您可能还会对开发的组合模块感兴趣，例如 CodePlex 上的 KwCombinatorics。

编辑 现在，用 LINQ 来救援：

private void cartesian1()
{
    textAppend("Cartesian 1");
    var setA = new[] { "whole wheat", "white", "rye" };
    var setB = new[] { "cold cut", "veggie", "turkey", "roast beef" };
    var setC = new[] { "everything", "just mayo" };

    var query =
        from bread in setA
        from meat in setB
        from toppings in setC
        let sandwich = String.Format("{1} on {0} with {2}",
            bread, meat, toppings)
        select sandwich;

    foreach( string sandwich in query )
    {
        textAppend(sandwich);
    }
}

Answer 6

@Guffa 答案的修改版本。我绝不是这段代码的创建者。

List<int> lists = new List<int> { 3, 2, 4 };

int[] cnt = new int[lists.Count];
int index;
do
{
    Console.WriteLine(String.Join(",", cnt));
    index = cnt.Length - 1;
    do
    {
        cnt[index] = (cnt[index] + 1) % lists[index];
    } while (cnt[index--] == 0 && index != -1);
} while (index != -1 || cnt[0] != 0);

使用 List 描述集合中元素的数量，而不是使用 List>（具有可能的值）。输出与原始答案相同。性能更好。