Generating a unique list of permutations, excluding ordering of elements

Question

So all the searches I find seem to give results that have unique permutations include the same set of values but in a different order.

So lets say I have an array:

int[] test = {1, 2, 3, 4};

The expected result sets are:

1
1,2
1,2,3
1,2,3,4
1,2,4
1,3
1,3,4
1,4
2
2,3
2,3,4
2,4
3
3,4
4

However, the results I am getting are:

1
1,2
1,2,3
1,2,3,4
2
2,3
2,3,4
3
3,4
4

As you can see, I am missing these results:

1,2,4
1,3
1,3,4
1,4
2,4

The code I am using is:

int[] test = {1, 2, 3, 4};
List<string> results = new List<string>();

for (int i = 0; i < test.Length;)
{
    results = prepareResults(test, results, "", test.Length);

    if (test.Length > 1)
    {
        int[] temp = new int[test.Length - 1];

        for (int j = 1; j < test.Length; j++)
        {
            temp[j - 1] = test[j];
        }

        test = temp;
    }
    else
    {
        break;
    }
}

public List<string> prepareResults(int[] dataSet, List<string> resultsList, string initialResult, int originalLength)
{
    while (dataSet.Length > 1)
    {
        if (initialResult.Length > 0)
        {
           initialResult += ",";
        }
        initialResult += dataSet[0].ToString();

        resultsList.Add(initialResult);

        int[] temp = new int[dataSet.Length - 1];

        for (int j = 1; j < dataSet.Length; j++)
        {
           temp[j - 1] = dataSet[j];
        }

        dataSet = temp;
        resultsList = prepareResults(dataSet, resultsList, initialResult, originalLength);
        return resultsList;
    }

    if (initialResult.Length != (originalLength * 2) - 1)
    {
        if (initialResult.Length > 0)
        {
            initialResult += ",";
        }

        initialResult += dataSet[0].ToString();
        resultsList.Add(initialResult);
    }

    return resultsList;
}

I am sure that I am just missing something stupid and obvious but I have been staring at this and trying different things for hours now, any suggestions?

`So all the searches I find seem to give results that have unique permutations include the same set of values but in a different order.` That's what permutations are. You are looking for [combinations](https://en.wikipedia.org/wiki/Combination). — JAD, Jul 13 '18 at 12:20
Possible duplicate of [How to Generate Combinations of Elements of a List in .NET 4.0](https://stackoverflow.com/questions/1119699/how-to-generate-combinations-of-elements-of-a-listt-in-net-4-0) — JAD, Jul 13 '18 at 12:23

Dmitry Bychenko · Accepted Answer · 2018-07-13T12:25:43.373

3

I suggest masking: we enumerate 2**n masks from 0000 to 1111 and apply these masks on the array items:

  mask | permutation
  ------------------
  0000 | (empty)
  0001 | 1
  0010 | 2
  0011 | 1, 2
  0100 | 3
  0101 | 1, 3
  ....
  1110 | 2, 3, 4
  1111 | 1, 2, 3, 4

Implementaton:

   int[] test = { 1, 2, 3, 4 };   

   var result = Enumerable
     .Range(0, 1 << test.Length)
     .Where(mask => mask != 0) // We don't want empty permutation
     .Select(mask => test 
        .Where((v, i) => ((1 << i) & mask) != 0)
        .ToArray());

   Console.Write(string.Join(Environment.NewLine, result
     .Select(item => string.Join(", ", item))));

Outcome:

1
2
1, 2
3
1, 3
2, 3
1, 2, 3
4
1, 4
2, 4
1, 2, 4
3, 4
1, 3, 4
2, 3, 4
1, 2, 3, 4

edited Jul 13 '18 at 12:25

answered Jul 13 '18 at 12:22

Dmitry Bychenko

180,369
20
160
215

1

Nice usage of LINQ there buddy :) – Juan Carlos Rodriguez Jul 13 '18 at 12:24
wouldn't `.Range(0, 1 << test.Length).Where(mask => mask != 0)` be replacable by `.Range(1, 1 << test.Length)`? – JAD Jul 13 '18 at 12:41
@JAD: You are quite right, but `.Range(1, 1 << test.Length - 1)` to be exact (please, notice `- 1`). I've tried to demonstrate the *general case*: creating *all* permutations (masks in `[0..2**N)` range) and then filtering out *required* ones (`Where`). – Dmitry Bychenko Jul 13 '18 at 12:45
Oh right, it's `(from, length)`, not `(from, to)`. – JAD Jul 13 '18 at 12:46
This works perfectly, thank you, now I just need to work out how I will work it with objects rather then simple integers. But that part is on me. Thanks for your help, I will mark it as the answer. – James Sunderland Jul 13 '18 at 21:29

Juan Carlos Rodriguez · Answer 2 · 2018-07-13T12:18:00.593

Every time I have had to use permutations I have used this method. It uses left-shift operator to iterate through all the possibilities. Give it a try.

    private List<List<int>> GetPermutations(List<int> testValues)
    {
        List<List<int>> result = new List<List<int>>();

        for (int count = 0; count < (1 << testValues.Count); ++count)
        {
            List<int> combinationList= new List<int>();

            for (int i = 0; i < testValues.Count; ++i)
            {
                if ((count & (1 << i)) == 0)
                {
                    combinationList.Add(testValues[i]);
                }
            }
            result.Add(combinationList);
        }

        return result;
    }

I don't know if you need to be exactly in the order you wrote you were expecting. If you need it to be in that order you should just apply linq to the result list :)

Generating a unique list of permutations, excluding ordering of elements

2 Answers2