How to find complex permutations based on and/or rules of lists of numbers, C#/Linq

Question

The current problem is that the code works, but it gets exponentially slower as more combinations are passed in. (The calculation takes > 5 seconds after 15 combinations are passed in.) I need to be able to pass in up to 100 combinations and still get a result back that takes less than 2 seconds.

I'm betting that a Linq query could solve this?

What I want to achieve:

{1, 2, 3} + {1, 5, 26, 40} = 12 combinations:
[1,1]
[1,5]
[1,26]
[1,40]
[2,1]
[2,5]
[2,26]
[2,40]
[3,1]
[3,5]
[3,26]
[3,40]

However, this example above only includes 2 combination sets. I should be able to pass in any number of combination sets.

The closest thing that looks like it is similar to what I want as an end result, due to being fast and efficient, is a linq query that handles most or all of the logic within it. Example: Getting all possible combinations from a list of numbers

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
              select
                  from i in Enumerable.Range(0, list.Count)
                  where (m & (1 << i)) != 0
                  select list[i];
}

Example of working code:

[Test]
public void StackOverflowExample_Simple()
{
    var list1 = new List<int>() { 1, 2, 3 };
    var list2 = new List<int>() { 1, 5, 26, 40 };

    var myListsOfNumberCombinations = new List<List<int>>() { list1, list2 };

    var results = GetAllPossibleCombinations(myListsOfNumberCombinations);

    Assert.AreEqual(12, results.Count());

    StringBuilder sb = new StringBuilder();
    foreach (var result in results)
    {
        foreach (var number in result.OrderBy(x => x))
        {
            sb.Append(number + ",");
        }
        sb.Append("|");
    }
    string finalResult = sb.ToString().Replace(",|", "|");

    Assert.AreEqual(finalResult, "1,1|1,5|1,26|1,40|1,2|2,5|2,26|2,40|1,3|3,5|3,26|3,40|");
}

[Test]
public void StackOverflowExample_TakesALongTime()
{
    var list1 = new List<int>() { 1, 2, 3 };
    var list2 = new List<int>() { 4, 5 };
    var list3 = new List<int>() { 1, 6 };
    var list4 = new List<int>() { 2, 5 };
    var list5 = new List<int>() { 1, 3, 55, 56 };
    var list6 = new List<int>() { 3, 4, 7, 8, 9 };

    var myListsOfNumberCombinations = new List<List<int>>() { list1, list2, list3, list4, list5, list1, list1, list1, list3, list4, list4, list5, list6, list6, list2 };


    DateTime startTime = DateTime.Now;

    var results = GetAllPossibleCombinations(myListsOfNumberCombinations);
    Assert.AreEqual(4147200, results.Count());

    var duration = DateTime.Now.Subtract(startTime).TotalSeconds;


    //duration = about 4 or 5 seconds
    Assert.Less(duration, 10); //easy place to put a breakpoint
}


public IEnumerable<IEnumerable<int>> GetAllPossibleCombinations(List<List<int>> combinationSets)
{
    List<List<int>> returnList = new List<List<int>>();

    _RecursiveGetMoreCombinations(
        ref returnList,
        new List<int>(),
        combinationSets,
        0);

    return returnList;
}

private void _RecursiveGetMoreCombinations(
    ref List<List<int>> returnList,
    List<int> appendedList,
    List<List<int>> combinationSets,
    int index)
{
    var combinationSet = combinationSets[index];

    foreach (var number in combinationSet)
    {
        List<int> newList = appendedList.AsEnumerable().ToList();
        newList.Add(number);

        if (combinationSets.Count() == index + 1)
        {
            returnList.Add(newList);
        }
        else
        {
            _RecursiveGetMoreCombinations(
                ref returnList,
                newList,
                combinationSets,
                index + 1);
        }
    }    
}

possible duplicate of [this]. Check out Eric Lippert's answer using LINQ standard operators. (http://stackoverflow.com/questions/3093622/generating-all-possible-combinations/3098381#3098381) — Farhad Alizadeh Noori, May 26 '14 at 20:26

score 0 · Answer 1 · answered May 26 '14 at 17:42

0

Can you not just do permutations of the first and third sets (the OR sets) and then place '45' (the AND set), or whatever the static numbers are, in between those numbers?

You don't need to include 4 and 5 (in this example) in the permutation logic if they are always going to be present.

answered May 26 '14 at 17:42

Steve

2,950
3
21
32

Thanks for that suggestion! I've reworked the code to not include any "AND" statements, and further simplified the code to help get a more precise answer to my question. – SED May 26 '14 at 18:38

How to find complex permutations based on and/or rules of lists of numbers, C#/Linq

1 Answers1