CODEWITHSUNDEEP
c#logiccombinatoricsmultiset
Andrea
Andrea

Reputation: 91

Non-boolean "truth table" creation

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:

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

TABLE:

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?

Upvotes: 4

Views: 611

Answers (4)

George Mauer
George Mauer

Reputation: 122132

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

Upvotes: 3

Kyle
Kyle

Reputation: 6684

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

Upvotes: 0

Andrey
Andrey

Reputation: 60075

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

Upvotes: 0

viraptor
viraptor

Reputation: 34175

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.

Upvotes: 2

Related Questions