c# - 生成唯一的排列列表，不包括元素的排序

Question

因此，我发现的所有搜索似乎都给出了具有独特排列的结果，包括相同的一组值，但顺序不同。

所以可以说我有一个数组：

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

预期的结果集是：

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

但是，我得到的结果是：

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

如您所见，我缺少这些结果：

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

我正在使用的代码是：

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

我确信我只是错过了一些愚蠢而明显的东西，但我一直盯着这个并尝试不同的东西几个小时，有什么建议吗？

标签： c#permutation

Answer 1

我建议屏蔽2**n：我们从0000to枚举掩码1111并将这些掩码应用于数组项：

  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  

实施：

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

结果：

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