Алгоритм для динамических комбинаций

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

Модифицированная версия ответа @ 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>, описывающее количество элементов в коллекции. Результат тот же, что и в оригинальном ответе. Производительность лучше.

Answer 3

Казалось бы, то, что вы действительно хотите , само по себе не является ни перестановкой, ни комбинацией. Вы хотите взглянуть на декартово произведение (см. здесь ) нескольких наборов, итерация по которым может включать в себя итерацию по комбинациям отдельных наборов.

Однако это не похоже на проблему комбинирования, потому что вы ищете способы выбрать 1 элемент из каждого набора. Количество способов сделать это - размер набора. Проблемы с комбинациями обычно включают выбор k -много из множества n -много вещей, где k = 1 или n тривиально .

Несколько методов создания итераторов в C # были обсуждены здесь . (Включая Джона Скита).

Если вы используете .NET, вас также могут заинтересовать разработанные модули комбинаторики, такие как KwCombinatorics в CodePlex.

edit Теперь с помощью 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 4

Поместите 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

У меня была похожая проблема некоторое время назад (генерация комбинаций), я использовал код из: http://www.merriampark.com/comb.htm. Это Java, но у меня не было проблем с переводом на C #.

Answer 6

Это проблема перестановки. Вы можете взглянуть на это:

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