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?

Answer 1

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

Answer 2

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 :)