Создание небулевой «таблицы истинности»

Question

У меня есть следующая проблема: мне нужно создать таблицу, которая представляет собой комбинацию значений, исходящих из наборов. Мощность элементов в наборе неизвестна и может варьироваться от множества к множеству, область значений неизвестна и может также варьироваться от множества к множеству. Элементы в наборе неотрицательны, по крайней мере два элемента находятся внутри набора. Далее следует пример:

• SET_A = {0, 1, 2}
• SET_B = {0, 1}
• Set_C = {0, 1}

Результат должен содержат следующие строки (порядок не является ограничивающим):

ТАБЛИЦА:

• | 0 0 0 |
• | 0 0 1 |
• | 0 1 0 |
• | 0 1 1 |
• | 1 0 0 |
• | 1 0 1 |
• | 1 1 0 |
• | 1 1 1 |
• | 2 0 0 |
• | 2 0 1 |
• | 2 1 0 |
• | 2 1 1 |

Кто-нибудь знает, какая математика стоит за этой проблемой? Я попытался рассмотреть проблемы Multiset, логические таблицы, комбинаторики. Многие из определений, которые я нашел, имеют сходство с моей проблемой, но я не могу изолировать что-либо в литературе, к которой я обращался до сих пор. Как только у меня есть ссылочное определение, я могу думать о его кодировании, но теперь я просто потерялся в рекурсивных функциях и ужасных играх с массивом. Благодарю.

EDIT: Вопрос был предложен уже: C# Permutation of an array of arraylists?

Answer 1

Редактировать: Извините, пришлось запустить прошлым вечером. Для произвольной размерности вы, вероятно, : придется использовать рекурсию. Вероятно, есть способ обойтись без него, но с рекурсией наиболее просто. Нижеследующее непроверено, но должно быть правильно.

IEnumerable<int[]> getRows(int[][] possibleColumnValues, int[] rowPrefix) { 
    if(possibleColumnValues.Any()) { //can't return early when using yield 
     var remainingColumns = possibleColumnValues.Skip(1).ToArray(); 
     foreach(var val in possibleColumnValues.First()) { 
      var rowSoFar = rowPrefix.Concat(new[]{val}).ToArray(); 
      yield return getRows(remainingColumns rowSoFar); 
     } 
    } 
} 

Использование:

getRows(new [][] { 
       new [] {0,1,2}, 
       new [] {0,1}, 
       new [] {0,1}, 
    }, new int[0]); 

Answer 2

Что вам смотреть на это комбинаторика. Также не имеет значения, что является доменом элементов в наборе. Пока вы можете перечислить их, проблема будет такой же, как для чисел от 0 до установленной мощности.

Чтобы перечислить все параметры, укажите вектор индексов и после каждого итерационного приращения первый индекс. Если он переполняется, установите значение 0 и увеличит второй индекс и т. Д.

Answer 3

Задача состоит в том, чтобы напечатать перестановки.Вы, кажется, копаете глубже, чем это. Это не имеет ничего общего с природой элементов.

Answer 4

Следующие данные не указаны для эффективности (ни в пространстве, ни в скорости). Идея состоит в том, чтобы просто получить базовый алгоритм. Я оставлю вам больше пространства и времени для вас.

Основная идея состоит в том, чтобы признать, что все комбинации списков n - это всего лишь комбинации из n-1 списков с каждым элементом первого списка. В этот момент это довольно прямая рекурсивная функция.

public static IEnumerable<int[]> Permute(params IEnumerable<int>[] sets) 
{ 
    if(sets.Length == 0) yield break; 
    if(sets.Length == 1) 
    { 
     foreach(var element in sets[0]) yield return new[] { element }; 
     yield break; 
    } 

    var first = sets.First(); 

    var rest = Permute(sets.Skip(1).ToArray()); 

    var elements = first.ToArray(); 

    foreach(var permutation in rest) 
    { 
     foreach(var element in elements) 
     { 
      var result = new int[permutation.Length + 1]; 
      result[0] = element; 
      Array.Copy(permutation, 0, result, 1, permutation.Length); 
      yield return result; 
     } 
    } 
}