CODEWITHSUNDEEP
c#arraysstringalgorithmrecursion
vi3x
vi3x

Reputation: 290

Permutations of string collections in C#

Seems like I'm stuck once again with recursive algorithms...

My application is supposed to sort files to different folders, according to the information specified by the user and according to a subfolder structure represented by a string like the following:

[ROOT] \ brand \ color \ material \

The tags in the structure string represent collections:

Assume:

var brand = new List<string> { "Nike", "Adidas", "Reebok" };
var color = new List<string> { "red", "blue", "yellow", "black" };
var material = new List<string> { "leather", "fabric" };

var data = new List<List<string>>() { brand, color, material };

And what I 'm trying to get is something like:

[ROOT]\Nike\red\leather
[ROOT]\Nike\red\fabric
[ROOT]\Nike\blue\leather
[ROOT]\Nike\blue\fabric
[ROOT]\Nike\yellow\leather
[ROOT]\Nike\yellow\fabric
[ROOT]\Nike\black\leather
[ROOT]\Nike\black\fabric
[ROOT]\Adidas\red\leather
[ROOT]\Adidas\red\fabric
[ROOT]\Adidas\blue\leather
[ROOT]\Adidas\blue\fabric
[ROOT]\Adidas\yellow\leather
[ROOT]\Adidas\yellow\fabric
[ROOT]\Adidas\black\leather
[ROOT]\Adidas\black\fabric
[ROOT]\Reebok\red\leather
[ROOT]\Reebok\red\fabric
[ROOT]\Reebok\blue\leather
[ROOT]\Reebok\blue\fabric
[ROOT]\Reebok\yellow\leather
[ROOT]\Reebok\yellow\fabric
[ROOT]\Reebok\black\leather
[ROOT]\Reebok\black\fabric

The problem is that the amount of data tags (brand, color, material) and their order is not known in advance, hence the need for recursion.

Any idea?

Thank you so much in advance!

Upvotes: 1

Views: 651

Answers (2)

navule
navule

Reputation: 3624

Here is the simple way by cross joining the current result with each member of the next one. For this, you also need to create any array that holds [ROOT].

        var root = new List<string> { "[ROOT]" };
        var brand = new List<string> { "Nike", "Adidas", "Reebok" };
        var color = new List<string> { "red", "blue", "yellow", "black" };
        var material = new List<string> { "leather", "fabric" };

        var data = new List<List<string>>() { root, brand, color, material };

        IEnumerable<string> lstComb = new List<string> { null };
        foreach (var list in data)
        {
            lstComb = lstComb.SelectMany(o => list.Select(s => $"{o}\\{s}".TrimStart(new char[]{'\\'})));
        }

Note: Order must be preserved when adding items to the data list that holds lists.

Upvotes: 0

L.B
L.B

Reputation: 116098

Here is the code By Eric Lippert. Cartesian Product..

http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    // base case: 
    IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
    foreach (var sequence in sequences)
    {
        var s = sequence; // don't close over the loop variable 
        // recursive case: use SelectMany to build the new product out of the old one 
        result =
            from seq in result
            from item in s
            select seq.Concat(new[] { item });
    }
    return result;
}

var result = CartesianProduct(new List<List<string>>() {brand,color,material });

Usage Example:

var brand = new List<string> { "Nike", "Adidas", "Reebok" };
var color = new List<string> { "red", "blue", "yellow", "black" };
var material = new List<string> { "leather", "fabric" };

foreach (var row in CartesianProduct(new List<List<string>>() { brand, color, material }))
{
    Console.WriteLine(String.Join(",", row));
}

Upvotes: 8

Related Questions