문제
일련의 숫자의 가능한 모든 조합을 포함하는 목록을 생성하는 LINQ를 만들 수 있습니까 ??
"21"을 입력하면 요소가있는 목록이 생성됩니다.
list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"
(그 순서대로 아님)
범위를 사용하여 다음과 같은 작업을 수행 할 수 있다는 것을 알고 있습니다.
List<char> letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations
AZ에서 알파벳을 생성합니다. 하지만 조합 생성기를 만들기 위해이 지식을 이전 할 수없는 것 같습니다.
나는 다음 코드로 그것을 알아낼 수 있었지만 너무 부피가 좋아 보이며 몇 줄로 수행 할 수 있다고 확신합니다. 정말 내가 만든 나쁜 해결책처럼 느껴집니다.
내가 전화했다고 상상해보십시오 GetAllCombinations("4321")
도움이된다면
public static String[] GetAllCombinations(String s)
{
var combinations = new string[PossibleCombinations(s.Length)];
int n = PossibleCombinations(s.Length - 1);
for (int i = 0; i < s.Length; i++)
{
String sub;
String[] subs;
if (i == 0)
{
sub = s.Substring(1); //Get the first number
}
else if (i == s.Length - 1)
{
sub = s.Substring(0, s.Length - 1);
}
else
{
sub = s.Substring(0, i) + s.Substring(i + 1);
}
subs = GetAllCombinations(sub);
for (int j = 0; j < subs.Length; j++)
{
combinations[i * n + j] = s[i] + subs[j];
}
}
return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
해결책
가치가있는 것은 다음과 같은 것을 시도하십시오.
public static IEnumerable<string> GetPermutations(string s)
{
if (s.Length > 1)
return from ch in s
from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
select string.Format("{0}{1}", ch, permutation);
else
return new string[] { s };
}
다른 팁
기록을 위해 : Josh의 대답 일반적인 방법 :
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
if (items.Count() > 1) {
return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
(item, permutation) => new[] { item }.Concat(permutation));
} else {
return new[] {items};
}
}
다음은 LINQ를 사용한 순열 및 조합 기능입니다
public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
if (source == null)
throw new ArgumentNullException("source");
yield return item;
foreach (var element in source)
yield return element;
}
public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
if (source == null)
throw new ArgumentNullException("source");
var list = source.ToList();
if (list.Count > 1)
return from s in list
from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
select p.Prepend(s);
return new[] { list };
}
public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
if (source == null)
throw new ArgumentNullException("source");
var list = source.ToList();
if (k > list.Count)
throw new ArgumentOutOfRangeException("k");
if (k == 0)
yield return Enumerable.Empty<TSource>();
foreach (var l in list)
foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
yield return c.Prepend(l);
}
DNA 알파벳 'a', 'c', 'g', 't':
var dna = new[] {'A', 'C', 'G', 'T'};
foreach (var p in dna.Permutate())
Console.WriteLine(String.Concat(p));
주어진
ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA
그리고 DNA 알파벳의 조합 (k = 2)
foreach (var c in dna.Combinate(2))
Console.WriteLine(String.Concat(c));
~이다
AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT
다른 사람들이 지적 했듯이이 페이지의 솔루션은 요소 중 하나가 동일하다면 중복을 생성합니다. 별개의 () 확장은이를 제거하지만 일반적으로 전체 검색 트리가 전환되기 때문에 확장 가능하지는 않습니다. 트래버스 중에 검색 공간을 상당히 다듬을 것입니다.
private static IEnumerable<string> Permute(string str)
{
if (str.Length == 0)
yield return "";
else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
foreach (var p in Permute(str.Remove(index, 1)))
yield return str[index] + p;
}
예제 문자열 "Bananabana"의 경우 트래버스 컬링을하지 않을 때 방문한 9,864,101과 달리 8,294 개의 노드가 방문됩니다.
이 순열 LINQ 확장을 사용할 수 있습니다.
foreach (var value in Enumerable.Range(1,3).Permute())
Console.WriteLine(String.Join(",", value));
결과가 발생합니다.
1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...
선택적으로 순열을 지정할 수 있습니다
foreach (var value in Enumerable.Range(1,2).Permute(4))
Console.WriteLine(String.Join(",", value));
결과:
1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2
추가 할 확장 클래스 :
public static class IEnumberableExtensions
{
public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}