我想得到一个数组中所有可能的数字排列-n!/K!n是数组的大小,k是相同数的个数。
例如,将有3(3!/2!)[3,0,0]的可能置换:
[3,0,0]
[0,3,0]
[0,0,3]
另一个例子是[2,1,0],它将产生6(3!/1!)排列:
[2,1,0]
[1,2,0]
[0,1,2]
[0,2,1]
[2,0,1]
[1,0,2]
我已经成功地使用了here中的代码:
static IEnumerable<IEnumerable<T>>
GetPermutationsWithRept<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutationsWithRept(list, length - 1)
.SelectMany(t => list,
(t1, t2) => t1.Concat(new T[] { t2 }));
}
生成置换后,我将运行
Sum()
来验证每个置换。然而,这可能不是一个有效的解决方案。有没有别的方法可以达到这个目的? 最佳答案
使用Sum
筛选GetPermutationsWithRept
的输出不正确考虑这个案例:
{1,2,3}
在本例中,GetPermutationsWithRept
的输出之一是{2,2,2}。总和相等(2+2+2=1+2+3)。但是,{2,2,2}不是有效的输出。
以下是基于您的方法的解决方案:
此类用于比较输出项(以计算不同的结果):
public class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>>
{
public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
{
return x.SequenceEqual(y);
}
public int GetHashCode(IEnumerable<T> obj)
{
return string.Join("-", obj.Select(x => x.ToString())).GetHashCode();
}
}
下面的代码调用
GetPermutationsWithRept
,并过滤两次结果。第一次删除{3,3,3}ad{2,2,2}等无效项,第二次删除重复项。var list = new int[] {1, 2, 3};
var result1 = GetPermutationsWithRept(list, 3).ToList();
var sorted_list = list.OrderBy(item => item).ToList();
var result2 = result1
.Where(rlist => rlist.OrderBy(x => x).SequenceEqual(sorted_list)) //first filter
.Distinct(new EnumerableComparer<int>()) //second filter
.ToList();
我认为在性能方面,这个解决方案对于大输入来说不是很好,但它是正确的。