2

我的代码有一个名为 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)
      }
}

但是我需要找到一种方法来为任何给定数量的 INPUTS 及其事件构建列表 iCOMBINATIONS。有任何想法吗？

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

C#（或 VB）

谢谢你

4

6 回答 6

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);
于 2010-04-12T06:39:54.643 回答
0

这是排列问题。你可以看看这个：

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

于 2010-04-12T06:18:03.037 回答
0

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

于 2010-04-12T06:21:20.453 回答
0

将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)
于 2010-04-12T06:46:01.663 回答
0

看起来你真正想要的，本身既不是排列，也不是组合。您想查看几个集合的笛卡尔积（参见此处），其中的迭代可能涉及对各个集合的组合进行迭代。

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

这里讨论了几种在 C# 中生成迭代器的方法。（包括 Jon Skeet 的作品）。

如果您使用的是 .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);
    }
}
于 2010-04-12T07:46:05.563 回答
0

@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<int>>- 使用可能的值 - 使用List<int>描述集合中元素的数量。输出与原始答案相同。性能更好。

于 2018-03-16T09:01:15.440 回答