Permutations of string collections in C#

Question

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!

When you receive a file you know it's properties right? Can't you create the folder on the fly using those properties? Where does recursion come into play? — Slugart
– Slugart, Commented Mar 9, 2014 at 22:09
var List<IEnumerable<string> data ... part is not going to compile. I don't see why you need this anyway. If your folder structure levels are fixed, you just need to iterate through each file, and work out which (sub)folder to put it into. — failedprogramming
– failedprogramming, Commented Mar 9, 2014 at 22:11
The user is dropping a file on the program interface, then he has to set the relevant metadata by choosing from menus in the UI. For a file there can even be 10 different metadata fields or so: all the detailed data is stored in a database, while the most important tags are creating a folder structure according to a structure string. This string is set in the config file, and its levels can be chosen by the user before starting the program. He can decide how many metadata fields he wants to use to create the string and their order. Therefore I don't know in advance how many iterations I need. — vi3x
– vi3x, Commented Mar 9, 2014 at 23:10
Please note: What is being requested here are technically combinations, not permutations. Permutations involve ordering so Nike\red\leather and leather\Nike\red would be two different, valid permutations. — RBarryYoung
– RBarryYoung, Commented May 29, 2015 at 13:29

Eric Lippert · Accepted Answer · 2014-03-10 20:23:13Z

8

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

edited Mar 10, 2014 at 20:23

Eric Lippert

663k185 gold badges1.3k silver badges2.1k bronze badges

answered Mar 9, 2014 at 22:11

L.B

116k20 gold badges189 silver badges229 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

vi3x Over a year ago

Works like a charm, thank you! I just needed to change parameter of CartesianProduct to a variable (my list of lists has arbitrary length) and it did exactly what I wanted. Also thank you for the reference!

Chris Over a year ago

@vi3x: I'm intrigued by what you mean by "I changed the parameter of CartesianProduct" to a variable. It would already accept an arbitrary number of lists of arbitrary length...

vi3x Over a year ago

@Chris, maybe I'm not too familiar with English (or programming!), but my function looks like "foreach (var row in CartesianProduct(ListOfLists)", where "ListOfLists" is populated at runtime. I don't know in advance how many and which sublists it will contain.

navule · Accepted Answer · 2019-05-23 09:26:48Z

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.

Collectives™ on Stack Overflow

Permutations of string collections in C#

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related