이 재귀 솔루션을 큰 소리로 외치고있다.
먼저 주어진 값 집합에서 특정 길이의 모든 조합을 생성하는 메소드를 만듭니다. 문자열 생성에만 관심이 있기 때문에 string이 불변이라는 사실을 활용할 수 있습니다 (P.D.2 참조). 재귀 함수를 구현하고 추론하는 것이 훨씬 쉬워집니다.
static IEnumerable<string> GetAllCombinations<T>(
ISet<T> set, int length)
{
IEnumerable<string> getCombinations(string current)
{
if (current.Length == length)
{
yield return current;
}
else
{
foreach (var s in set)
{
foreach (var c in getCombinations(current + s))
{
yield return c;
}
}
}
}
return getCombinations(string.Empty);
}
이 방법이 어떻게 작동하는지주의 깊게 연구하십시오. 그것을 이해하기 위해 작은 예제를 위해 손으로 직접 작업하십시오.
지금, 한 번 우리는 가능한 모든 조합을 생성하는 방법을 알고, 문자열을 구축하는 것은 쉽다 : 지정된 문자열에 와일드 카드의 수 밖으로
- 그림이 우리의 결합 길이 될 것입니다.
- 모든 조합에 대해 각 문자를 와일드 카드가있는 문자열에 순서대로 삽입하십시오.
public static IEnumerable<string> GenerateCombinations<T>(
this string s,
IEnumerable<T> set,
char wildcard)
{
var length = s.Count(c => c == wildcard);
var combinations = GetAllCombinations(set, length);
var builder = new StringBuilder();
foreach (var combination in combinations)
{
var index = 0;
foreach (var c in s)
{
if (c == wildcard)
{
builder.Append(combination[index]);
index += 1;
}
else
{
builder.Append(c);
}
}
yield return builder.ToString();
builder.Clear();
}
}
그리고 우리는 완료 :
좋아, 그냥 작업을 수행 할 수 있습니다. 사용법은 다음과 같습니다
var set = new HashSet<int>(new[] { 1, 2, 3, 4 });
Console.WriteLine(
string.Join("; ", "[email protected]@d".GenerateCombinations(set, '@')));
그리고 확실히 충분히, 출력은 다음과 같습니다
a1bc1d; a1bc2d; a1bc3d; a1bc4d; a2bc1d; a2bc2d; a2bc3d;
a2bc4d; a3bc1d; a3bc2d; a3bc3d; a3bc4d; a4bc1d; a4bc2d;
a4bc3d; a4bc4d
이 가장 성능이 좋은 또는 효율적인 구현인가? 아마 읽을 수없고 유지할 수있는 것은 아닙니다. 회의가 아닌 특정 성과 목표를 가지고 있지 않다면 효과가 있고 이해하기 쉬운 코드를 작성하십시오.
경찰서. 모든 오류 처리 및 인수 유효성 검사를 생략했습니다.
P.D.2 : 조합의 길이가 큰 경우 GetAllCombinations 내부의 연결 문자열은 좋지 않을 수 있습니다. 이 경우 GetAllCombinations을 IEnumerable<IEnumerable<T>>으로 보내고 ImmutableStack<T>을 구현하고 string 대신 조합 버퍼로 사용하십시오.
