我正在从这里构建代码。我想生成一个集合的所有排列，例如（取自线程）：
Collection: 1, 2, 3
Permutations: {1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
相反，我只想生成不同的排列。如果我们这样做，只有
剩余的排列，因为18个项目是相同的（k）。
现在，我可以运行上述线程的代码，并将结果存储在一个HashSet中，消除重复的排列。然而，这将是非常低效的。我在寻找一种算法来直接生成有区别的排列。
使用交换算法查找排列，您可以直接排除产生重复排列的部分。该算法可在互联网上使用，您可以找到有关它的更多信息。
private static void Main(string[] args)
{
List<int> set = new List<int>
{
20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
var permutes = Permute(set);
Console.WriteLine(permutes.Count); // outputs 58140
}
private static List<int[]> Permute(List<int> set)
{
List<int[]> result = new List<int[]>();
Action<int> permute = null;
permute = start =>
{
if (start == set.Count)
{
result.Add(set.ToArray());
}
else
{
List<int> swaps = new List<int>();
for (int i = start; i < set.Count; i++)
{
if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
swaps.Add(set[i]);
Swap(set, start, i);
permute(start + 1);
Swap(set, start, i);
}
}
};
permute(0);
return result;
}
private static void Swap(List<int> set, int index1, int index2)
{
int temp = set[index1];
set[index1] = set[index2];
set[index2] = temp;
}
下图显示了交换算法的工作原理。
因此，您有{A，B，C}，{A，C，B}，{B，A，C}、{B，C，A}，{C，B，A}、{C，A，B}
现在考虑< code>A和< code>B相等。我用photoshop编辑了这张图片(对不起，如果我不擅长的话！)并将< code>B替换为< code>A。正如你在图片中看到的
我在图像中发现了重复。如果您跳过它们，您将拥有< code>{A，A，C}、{A，C，A}、{C，A，A}
您必须存储交换的项目，因此如果项目相等并且我们已经进行了交换，我们只需跳过以防止欺骗
if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
swaps.Add(set[i]); // else add it to the list of swaps.
为了测试，如果你删除这部分，那么这个算法将产生重复的排列，控制台将输出n！。
这是迄今为止我想到的最好的解决方案。欢迎提出优化建议。它正好返回n！/k！项目。
置换{ 20，4，3，3，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0 }大约需要一秒钟。
private static IEnumerable<int[]> Permute(int[] list)
{
if (list.Length > 1)
{
int n = list[0];
foreach (int[] subPermute in Permute(list.Skip(1).ToArray()))
{
for (int index = 0; index <= subPermute.Length; index++)
{
int[] pre = subPermute.Take(index).ToArray();
int[] post = subPermute.Skip(index).ToArray();
if (post.Contains(n))
continue;
yield return pre.Concat(new[] { n }).Concat(post).ToArray();
}
}
}
else
{
yield return list;
}
}
让我们试试：
Knuths
1. Find the largest index j such that a[j] < a[j + 1]. If no
such index exists, the permutation is the last permutation.
{20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
> > = = = = = = = = = = = = = = = = =
糟糕，没有索引< code>j使得< code>a[j]
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20}
1. Find the largest index j such that a[j] < a[j + 1]. If no
such index exists, the permutation is the last permutation.
j = 18 since a[18] < a[19]
2. Find the largest index l such that a[j] < a[l]. Since j + 1
is such an index, l is well defined and satisfies j < l.
l = 19 since a[18] < a[19]
3. Swap a[j] with a[l].
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}
让我们再做几个:
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,20}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20,0}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,0,10}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10,0}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,20}
...
如您所见，大元素稳定地(明显地)向左移动，直到:
{10,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
yields {20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
并且结束而不重复排列。
