C# - 순열(Permutation) 예제 코드
조합이 나오면,
C# - 조합(Combination) 예제 코드
; https://www.sysnet.pe.kr/2/0/10954
빠지지 않는 것이 바로 순열입니다. 위의 조합 코드를 만든
James McCaffrey가 순열도 만들어 놓았기 때문에 그대로 사용해도 좋습니다. ^^
Using Permutations in .NET for Improved Systems Security
; http://delphi.ktop.com.tw/download/upload/41338_Using%20Permutations%20in%20.NET%20for%20Improved%20Systems%20Security.doc
namespace ConsoleApplication1
{
class Permutation
{
private int[] data = null;
private int order = 0;
public Permutation(int n)
{
this.data = new int[n];
for (int i = 0; i < n; ++i)
{
this.data[i] = i;
}
this.order = n;
}
public Permutation Successor()
{
if (this.order <= 1)
{
return null;
}
Permutation result = new Permutation(this.order);
int left, right;
for (int k = 0; k < result.order; ++k) // Step #0 - copy current data into result
{
result.data[k] = this.data[k];
}
left = result.order - 2; // Step #1 - Find left value
while ((result.data[left] > result.data[left + 1]) && (left >= 1))
{
--left;
}
if ((left == 0) && (this.data[left] > this.data[left + 1]))
{
return null;
}
right = result.order - 1; // Step #2 - find right; first value > left
while (result.data[left] > result.data[right])
{
--right;
}
int temp = result.data[left]; // Step #3 - swap [left] and [right]
result.data[left] = result.data[right];
result.data[right] = temp;
int i = left + 1; // Step #4 - order the tail
int j = result.order - 1;
while (i < j)
{
temp = result.data[i];
result.data[i++] = result.data[j];
result.data[j--] = temp;
}
return result;
}
internal static long Choose(int length)
{
long answer = 1;
for (int i = 1; i <= length; i ++)
{
checked { answer = answer * i; }
}
return answer;
}
public string[] ApplyTo(string[] arr)
{
if (arr.Length != this.order)
{
return null;
}
string[] result = new string[arr.Length];
for (int i = 0; i < result.Length; ++i)
{
result[i] = arr[this.data[i]];
}
return result;
}
public override string ToString()
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
sb.Append("( ");
for (int i = 0; i < this.order; ++i)
{
sb.Append(this.data[i].ToString() + " ");
}
sb.Append(")");
return sb.ToString();
}
}
}
같은 사람이 만들었기 때문에 사용법도 순열과 매우 흡사하게 구성됩니다.
string[] items = new string[] { "apple", "banana", "cherry" };
Permutation c = new Permutation(items.Length);
string[] snapshot = null;
while (c != null)
{
snapshot = c.ApplyTo(items);
DisplayItems(snapshot);
c = c.Successor();
}
/*
출력 결과:
{ apple, banana, cherry }
{ apple, cherry, banana }
{ banana, apple, cherry }
{ banana, cherry, apple }
{ cherry, apple, banana }
{ cherry, banana, apple }
*/
또한, 제네릭과 IEnumerable 메서드를 추가 적용해 보면,
public class Permutation<TData> : IEnumerable<TData[]>
{
private int[] data = null;
private int order = 0;
private TData[] elems;
public Permutation(TData[] items)
{
this.order = items.Length;
this.data = new int[this.order];
this.elems = items;
for (int i = 0; i < this.order; ++i)
{
this.data[i] = i;
}
}
public Permutation<TData> Successor()
{
if (this.order <= 1)
{
return null;
}
Permutation<TData> result = new Permutation<TData>(this.elems);
int left, right;
for (int k = 0; k < result.order; ++k) // Step #0 - copy current data into result
{
result.data[k] = this.data[k];
}
left = result.order - 2; // Step #1 - Find left value
while ((result.data[left] > result.data[left + 1]) && (left >= 1))
{
--left;
}
if ((left == 0) && (this.data[left] > this.data[left + 1]))
{
return null;
}
right = result.order - 1; // Step #2 - find right; first value > left
while (result.data[left] > result.data[right])
{
--right;
}
int temp = result.data[left]; // Step #3 - swap [left] and [right]
result.data[left] = result.data[right];
result.data[right] = temp;
int i = left + 1; // Step #4 - order the tail
int j = result.order - 1;
while (i < j)
{
temp = result.data[i];
result.data[i++] = result.data[j];
result.data[j--] = temp;
}
return result;
}
internal static long Choose(int length)
{
long answer = 1;
for (int i = 1; i <= length; i++)
{
checked { answer = answer * i; }
}
return answer;
}
public TData[] ApplyTo(TData[] arr)
{
if (arr.Length != this.order)
{
return null;
}
TData[] result = new TData[arr.Length];
for (int i = 0; i < result.Length; ++i)
{
result[i] = arr[this.data[i]];
}
return result;
}
public override string ToString()
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
sb.Append("( ");
for (int i = 0; i < this.order; ++i)
{
sb.Append(this.data[i].ToString() + " ");
}
sb.Append(")");
return sb.ToString();
}
public IEnumerator<TData[]> GetEnumerator()
{
Permutation<TData> p = new Permutation<TData>(this.elems);
TData[] snapshot = null;
while (p != null)
{
snapshot = p.ApplyTo(this.elems);
yield return snapshot;
p = p.Successor();
}
}
IEnumerator IEnumerable.GetEnumerator()
{
Permutation<TData> p = new Permutation<TData>(this.elems);
TData[] snapshot = null;
while (p != null)
{
snapshot = p.ApplyTo(this.elems);
yield return snapshot;
p = p.Successor();
}
}
}
배열의 요소 타입에 상관없이 사용할 수 있습니다.
{
string[] items = new string[] { "apple", "banana", "cherry" };
Permutation<string> p = new Permutation<string>(items);
foreach (var result in p)
{
PrintElems(result);
}
}
{
int[] items = new int[] { 1, 2, 3 };
Permutation<int> p = new Permutation<int>(items);
foreach (var result in p)
{
PrintElems(result);
}
}
private static void PrintElems(T[] elems)
{
Console.Write("{ ");
foreach (var elem in elems)
{
Console.Write(elem + ", ");
}
Console.WriteLine("}");
}
/* 출력 결과
{ apple, banana, cherry, }
{ apple, cherry, banana, }
{ banana, apple, cherry, }
{ banana, cherry, apple, }
{ cherry, apple, banana, }
{ cherry, banana, apple, }
{ 1, 2, 3, }
{ 1, 3, 2, }
{ 2, 1, 3, }
{ 2, 3, 1, }
{ 3, 1, 2, }
{ 3, 2, 1, }
*/
첨부한 파일은, "
Using Permutations in .NET for Improved Systems Security" 워드 파일과
이 글의 예제 코드입니다.
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]