使用相同字母的排列
我目前正在研究一个项目,我需要从给定的一组字符中生成所有可能的排列。我目前使用此代码:使用相同字母的排列
public static IEnumerable<string> AllPermutations(this IEnumerable<char> s)
{
return s.SelectMany(x =>
{
var index = Array.IndexOf(s.ToArray(), x);
return s.Where((y, i) => i != index).AllPermutations().Select(y => new string(new[] { x }.Concat(y).ToArray())).Union(new[] { new string(new[] { x }) });
}).Distinct();
}
从this答案。
我遇到的问题是它不会生成多次使用相同字母的permuations。
例如,如果我用abcde
作为输入我需要它像aaaaa
和dcc
等
我没有足够的经验与LINQ来理解代码停止重复的字母组合产生。任何帮助是极大的赞赏。
这威力工作,但我敢肯定,它可以更有效地进行(以计数提示从PeskyGnat):
static IEnumerable<string> GetVariations(string s)
{
int[] indexes = new int[s.Length];
StringBuilder sb = new StringBuilder();
while (IncrementIndexes(indexes, s.Length))
{
sb.Clear();
for (int i = 0; i < indexes.Length; i++)
{
if (indexes[i] != 0)
{
sb.Append(s[indexes[i]-1]);
}
}
yield return sb.ToString();
}
}
static bool IncrementIndexes(int[] indexes, int limit)
{
for (int i = 0; i < indexes.Length; i++)
{
indexes[i]++;
if (indexes[i] > limit)
{
indexes[i] = 1;
}
else
{
return true;
}
}
return false;
}
编辑:更改为使用收益率回报每罗林斯建议。如果您不需要保留所有结果,并且可以在全部生成结果之前开始使用结果,则可以更好地利用内存。
这绝对是辉煌!我不能够感谢你。 +1并接受,谢谢! – 2012-03-09 14:48:28
无论这种做法是否可以更有效地完成,我相信它可以做得更低效。例如。我的回答:D – Rawling 2012-03-09 14:50:43
@Rawling:其实我的一件事情不会这样做,那就是处理重复。例如,如果字符串是“cca”,那么我会两次吐出“caa”,一次对于每个看起来不同的“c”。你们不这样做。 – 2012-03-09 15:03:40
我很惊讶这个作品。它基本上是“从字符中创建一个字符串列表,然后对从列表中取出的每个字符串,再次添加每个字符,并将结果字符串添加到列表中,重复,直到得到正确的长度。
public static IEnumerable<string> BuildStrings(this IEnumerable<char> alphabet)
{
var strings = alphabet.Select(c => c.ToString());
for (int i = 1; i < alphabet.Count(); i++)
{
strings = strings.Union(strings.SelectMany(s => alphabet.Select(c => s + c.ToString())));
}
return strings;
}
啊哈,它只会工作,因为我在做'联合'而不是'康卡特',否则我会有许多重复的... – Rawling 2012-03-09 15:12:29
通过固定点运营商只使用递归的lambda(THX @Rawling为的SelectMany)
// Fix point operator
public static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
{
return t => f(Fix<T, TResult>(f))(t);
}
然后
var chars = new[] {'a','b','c','d','e'}.Select(c=>c.ToString()) ;
var result = Fix<int,IEnumerable<string>>(
f =>
x =>
x == 1
? chars
: chars.Union(f(x - 1).SelectMany(s => chars.Select(c => s + c))))(chars.Count());
有什么理由这样做一个有趣的一个在LINQ中? – 2012-03-09 13:54:10
我没有写这个,所以只是寻找真正做到这个工作的代码。 – 2012-03-09 13:54:58
'aaaaa'不是'abcde'的排列组合。如果你的项目需要排列不包括'aaaaa',如果你包含'aaaaa',不要把它称为排列(或者组合)。你只会混淆每个人阅读你的问题,包括你自己。 – 2012-03-09 13:55:52