Non-boolean "truth table" creation

Question

I have the following problem: I need to create a table, which is combination of values coming from sets. The cardinality of the elements in the set is unknown, and may vary from set to set, the domain of the values is unknown, and may as well vary from set to set. The elements in the set are non-negative, at least two elements are within a set. Here follows an example:

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

The result should contain the following rows (order is not a constraint):

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 |

Does anybody know which is the Mathematics behind this problem? I tried to look at Multiset problems, logic tables, combinatorics. Many of the definitions that I found have similarities to my problem, but I can't isolate anything in the literature that I have accessed so far. Once I have a reference definition I can think of coding it, but now I just got lost in recursive functions and terrible array-index games. Thanks.

EDIT: Question was proposed already at: C# Permutation of an array of arraylists?

I'm not sure what the sets you posted have to do with your table. can you please explain the relationship? — George Mauer, Feb 02 '15 at 23:27
@GeorgeMauer table contains all combinations of all possible set values. — holgac, Feb 02 '15 at 23:27
I don't know C# much but in python, this is a perfect example for generator/yield usage. yield exists in C#; there probably is a way to construct the desired table using yield. example in python: http://pastebin.com/zveXyd0S — holgac, Feb 02 '15 at 23:29

George Mauer · Accepted Answer · 2015-02-03T16:53:46.003

3

Edit: Sorry, had to run last evening. For arbitrary dimensionality you probably would have to use recursion. There's probably a way to do without it, but with recursion is most straightforward. The below is untested but should be about right.

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);
        }
    }
}

Usage:

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

edited Feb 03 '15 at 16:53

answered Feb 02 '15 at 23:38

George Mauer

117,483
131
382
612

Wow, ok it works, but is it possible to extend this functionality to a collection of arrays? (from pos1 to posN created dynamically), I have a dynamic collection of arrays, I don't know how many they will come. I tried this: http://pastebin.com/jV6pfMdh – Andrea Feb 03 '15 at 00:07
@user3200743 Sorry I had to run out last evening. check my edit. I think its a lot simpler than the accepted answer. – George Mauer Feb 03 '15 at 15:40
ME LIKE IT ;) I found another available recursive solution, but I will probably choose yours anyway. 6 lines of code, I like it. Have a good day. – Andrea Feb 06 '15 at 00:08

score 2 · Answer 2 · answered Feb 02 '15 at 23:27

2

The thing you look for is combinatorics. Also it doesn't really matter what is the domain of the elements in set. As long as you can enumerate them, the problem is the same as for numbers from 0 to the set cardinality.

To enumerate all options, have a vector of indices and after each iteration increment the first index. If it overflows, set to 0 and increment the second index, etc.

answered Feb 02 '15 at 23:27

viraptor

33,322
10
107
191

Combinatorics is a quite big branch, and I get lost in the wild forest of definitions.Regarding your solution, what do you mean with index? Is it the index of the element in the set (if you think of an array representation), or something else (maybe regarding the table itself) – Andrea Feb 02 '15 at 23:36

score 0 · Answer 3 · answered Feb 02 '15 at 23:53

0

The task is to print permutations. You seem to dig deeper then it is. It has nothing to do with nature of elements.

answered Feb 02 '15 at 23:53

Andrey

59,039
12
119
163

Since I don't know the number of sets, nor the number of elements in them. I find it difficult to implement (I can't easily define rules for building the table when these two constraints do not hold anymore). I take the first set, then I try to build the permutation considering the second set, and then the third, but how can I stop? I tried a recursive function approach, but which would be the condition of termination? (or maybe I am tired and need some sleep ;) ) – Andrea Feb 03 '15 at 00:12
@user3200743 see my solution. The condition for termination is there are no more columns left to process – George Mauer Feb 03 '15 at 16:53

score 0 · Answer 4 · answered Feb 03 '15 at 00:40

The following is not written for efficiency (neither in space nor speed). The idea is to just get the basic algorithm across. I'll leave making this more space and time efficient up to you.

The basic idea is to recognize that all the combinations of n lists, is just all the combinations of n-1 lists with each element of the first list tacked on. It's a pretty straight-forward recursive function at that point.

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

Non-boolean "truth table" creation

4 Answers4