非布尔 "truth table" 创建

Question

我遇到以下问题：我需要创建一个 table，它是来自集合的值的组合。集合中元素的基数是未知的，并且可能因集合而异，值的域是未知的，并且也可能因集合而异。集合中的元素是非负的，至少有两个元素在一个集合中。下面是一个例子：

SET_A = { 0, 1, 2 }
SET_B = { 0, 1 }
SET_C = { 0, 1 }

结果应包含以下行（顺序不受约束）：

TABLE:

| 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 |

有人知道这个问题背后的数学原理是什么吗？我试图研究多重集问题、逻辑 tables、组合学。我发现的许多定义与我的问题有相似之处，但我无法从目前所访问的文献中分离出任何内容。一旦有了参考定义，我就可以考虑对其进行编码，但现在我只是迷失在递归函数和糟糕的数组索引游戏中。谢谢

编辑：已在以下位置提出问题： C# Permutation of an array of arraylists?

Answer 1

你要找的是组合数学。同样，集合中元素的域是什么并不重要。只要能枚举出来，问题就和从0到设定基数的数字一样。

要枚举所有选项，有一个索引向量，并在每次迭代后递增第一个索引。如果溢出，设置为0并递增第二个索引等

Answer 2

编辑： 抱歉，昨晚不得不运行。对于任意维度，您可能将必须使用递归。没有它可能有一种方法，但是递归是最直接的。以下未经测试，但应该是正确的。

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 3

任务是打印排列。你似乎挖得更深了。与元素的性质无关。

Answer 4

下面不是为了效率而写的（既不在space也不速度）。这个想法只是让基本算法通过。 space 和时间效率由您决定。

基本思想是认识到 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;
        }
    }
}

非布尔 "truth table" 创建

Non-boolean "truth table" creation

c#

logic

combinatorics

multiset