반응형
집합의 순열 생성 (가장 효율적)
다음과 같이 집합 (컬렉션)의 모든 순열을 생성하고 싶습니다.
Collection: 1, 2, 3
Permutations: {1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
이것은 일반적으로 "어떻게"에 대한 질문이 아니라 가장 효율적인 방법에 관한 것입니다. 또한 모든 순열을 생성하고 반환하고 싶지는 않지만 한 번에 하나의 순열 만 생성하고 필요한 경우에만 계속합니다 (반복자처럼 시도했지만 그보다 적은 것으로 판명 됨). 실력 있는).
나는 많은 알고리즘과 접근 방식을 테스트했고 내가 시도한 것 중 가장 효율적인 코드를 생각 해냈다.
public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
// More efficient to have a variable instead of accessing a property
var count = elements.Length;
// Indicates whether this is the last lexicographic permutation
var done = true;
// Go through the array from last to first
for (var i = count - 1; i > 0; i--)
{
var curr = elements[i];
// Check if the current element is less than the one before it
if (curr.CompareTo(elements[i - 1]) < 0)
{
continue;
}
// An element bigger than the one before it has been found,
// so this isn't the last lexicographic permutation.
done = false;
// Save the previous (bigger) element in a variable for more efficiency.
var prev = elements[i - 1];
// Have a variable to hold the index of the element to swap
// with the previous element (the to-swap element would be
// the smallest element that comes after the previous element
// and is bigger than the previous element), initializing it
// as the current index of the current item (curr).
var currIndex = i;
// Go through the array from the element after the current one to last
for (var j = i + 1; j < count; j++)
{
// Save into variable for more efficiency
var tmp = elements[j];
// Check if tmp suits the "next swap" conditions:
// Smallest, but bigger than the "prev" element
if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
{
curr = tmp;
currIndex = j;
}
}
// Swap the "prev" with the new "curr" (the swap-with element)
elements[currIndex] = prev;
elements[i - 1] = curr;
// Reverse the order of the tail, in order to reset it's lexicographic order
for (var j = count - 1; j > i; j--, i++)
{
var tmp = elements[j];
elements[j] = elements[i];
elements[i] = tmp;
}
// Break since we have got the next permutation
// The reason to have all the logic inside the loop is
// to prevent the need of an extra variable indicating "i" when
// the next needed swap is found (moving "i" outside the loop is a
// bad practice, and isn't very readable, so I preferred not doing
// that as well).
break;
}
// Return whether this has been the last lexicographic permutation.
return done;
}
사용법은 요소 배열을 보내고 이것이 마지막 사전 순열인지 여부를 나타내는 부울을 반환하고 배열을 다음 순열로 변경하는 것입니다.
사용 예 :
var arr = new[] {1, 2, 3};
PrintArray(arr);
while (!NextPermutation(arr))
{
PrintArray(arr);
}
문제는 내가 코드의 속도에 만족하지 않는다는 것입니다.
크기가 11 인 배열의 모든 순열을 반복하는 데 약 4 초가 걸립니다. 인상적이라고 생각할 수 있지만, 크기 11 세트의 가능한 순열의 양은 11!거의 4 천만에 달하기 때문입니다.
논리적으로 크기가 12 인 배열의 경우 12!is 이므로 약 12 배 더 많은 시간 11! * 12이 걸리며 크기가 13 인 배열의 경우 크기 12의 경우보다 약 13 배 더 많은 시간이 걸립니다.
따라서 크기가 12 이상인 배열에서 모든 순열을 처리하는 데 실제로 시간이 얼마나 걸리는지 쉽게 이해할 수 있습니다.
그리고 나는 어떻게 든 그 시간을 많이 줄일 수 있다는 강한 예감이 있습니다 (C # 이외의 언어로 전환하지 않고-컴파일러 최적화는 실제로 꽤 잘 최적화되기 때문에 어셈블리에서 수동으로 잘 최적화 할 수 있을지 의문입니다).
누구든지 더 빨리 처리 할 수있는 다른 방법을 알고 있습니까? 현재 알고리즘을 더 빠르게 만드는 방법에 대한 아이디어가 있습니까?
이를 위해 외부 라이브러리 나 서비스를 사용하고 싶지 않습니다. 코드 자체를 갖고 싶고 가능한 한 인간적으로 효율적 이길 원합니다.
2018-05-28 업데이트 :
- 새로운 다중 스레드 버전 (훨씬 더 빠름)은 다른 답변으로 아래에서 사용할 수 있습니다.
- 또한 순열에 대한 기사 : 순열 : 빠른 구현 및 멀티 스레딩을 허용하는 새로운 색인 생성 알고리즘
너무 늦었 어 ...
최근 테스트에 따르면 (2018 년 5 월 22 일 업데이트 됨)
- 가장 빠르지 만 사전 순서는 아닙니다.
- 가장 빠른 사전 순서를 위해 Sani Singh Huttunen 솔루션이가는 길인 것 같습니다.
내 컴퓨터 (밀리 초)에 릴리스 된 10 개 항목 (10!)에 대한 성능 테스트 결과 :
- 우 엘렛 : 29
- SimpleVar : 95
- 에레 스 로빈슨 : 156
- Sani Singh Huttunen : 37
- 펑양 : 45047
내 컴퓨터에 출시 된 13 개 항목 (13!)에 대한 성능 테스트 결과 (초) :
- 우 엘렛 : 48.437
- SimpleVar : 159.869
- 에레 스 로빈슨 : 327.781
- Sani Singh Huttunen : 64.839
내 솔루션의 장점 :
- 힙 알고리즘 (단일 스왑 순열)
- 곱셈 없음 (웹에서 볼 수있는 일부 구현)
- 인라인 스왑
- 일반적인
- 안전하지 않은 코드 없음
- 제자리에 있음 (매우 낮은 메모리 사용량)
- 모듈로 없음 (첫 번째 비트 만 비교)
힙의 알고리즘 구현 :
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
namespace WpfPermutations
{
/// <summary>
/// EO: 2016-04-14
/// Generator of all permutations of an array of anything.
/// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
/// </summary>
public static class Permutations
{
/// <summary>
/// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
/// </summary>
/// <param name="items">Items to permute in each possible ways</param>
/// <param name="funcExecuteAndTellIfShouldStop"></param>
/// <returns>Return true if cancelled</returns>
public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
{
int countOfItem = items.Length;
if (countOfItem <= 1)
{
return funcExecuteAndTellIfShouldStop(items);
}
var indexes = new int[countOfItem];
for (int i = 0; i < countOfItem; i++)
{
indexes[i] = 0;
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
for (int i = 1; i < countOfItem;)
{
if (indexes[i] < i)
{ // On the web there is an implementation with a multiplication which should be less efficient.
if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same.
{
Swap(ref items[i], ref items[indexes[i]]);
}
else
{
Swap(ref items[i], ref items[0]);
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
indexes[i]++;
i = 1;
}
else
{
indexes[i++] = 0;
}
}
return false;
}
/// <summary>
/// This function is to show a linq way but is far less efficient
/// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="length"></param>
/// <returns></returns>
static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
/// <summary>
/// Swap 2 elements of same type
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
/// <summary>
/// Func to show how to call. It does a little test for an array of 4 items.
/// </summary>
public static void Test()
{
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
Console.WriteLine("Ouellet heap's algorithm implementation");
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
Console.WriteLine("Linq algorithm");
foreach (var v in GetPermutations(values, values.Length))
{
Console.WriteLine(String.Join("", v));
}
// Performance Heap's against Linq version : huge differences
int count = 0;
values = new int[10];
for (int n = 0; n < values.Length; n++)
{
values[n] = n;
}
Stopwatch stopWatch = new Stopwatch();
ForAllPermutation(values, (vals) =>
{
foreach (var v in vals)
{
count++;
}
return false;
});
stopWatch.Stop();
Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
count = 0;
stopWatch.Reset();
stopWatch.Start();
foreach (var vals in GetPermutations(values, values.Length))
{
foreach (var v in vals)
{
count++;
}
}
stopWatch.Stop();
Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
}
}
}
이것은 내 테스트 코드입니다.
Task.Run(() =>
{
int[] values = new int[12];
for (int n = 0; n < values.Length; n++)
{
values[n] = n;
}
// Eric Ouellet Algorithm
int count = 0;
var stopwatch = new Stopwatch();
stopwatch.Reset();
stopwatch.Start();
Permutations.ForAllPermutation(values, (vals) =>
{
foreach (var v in vals)
{
count++;
}
return false;
});
stopwatch.Stop();
Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
// Simple Plan Algorithm
count = 0;
stopwatch.Reset();
stopwatch.Start();
PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
permutations2.Permutate(1, values.Length, (int[] vals) =>
{
foreach (var v in vals)
{
count++;
}
});
stopwatch.Stop();
Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
// ErezRobinson Algorithm
count = 0;
stopwatch.Reset();
stopwatch.Start();
foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
{
foreach (var v in vals)
{
count++;
}
};
stopwatch.Stop();
Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
});
사용 예 :
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
이것은 당신이 찾고있는 것일 수 있습니다.
private static bool NextPermutation(int[] numList)
{
/*
Knuths
1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
3. Swap a[j] with a[l].
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
*/
var largestIndex = -1;
for (var i = numList.Length - 2; i >= 0; i--)
{
if (numList[i] < numList[i + 1]) {
largestIndex = i;
break;
}
}
if (largestIndex < 0) return false;
var largestIndex2 = -1;
for (var i = numList.Length - 1 ; i >= 0; i--) {
if (numList[largestIndex] < numList[i]) {
largestIndex2 = i;
break;
}
}
var tmp = numList[largestIndex];
numList[largestIndex] = numList[largestIndex2];
numList[largestIndex2] = tmp;
for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {
tmp = numList[i];
numList[i] = numList[j];
numList[j] = tmp;
}
return true;
}
음, C로 처리 한 다음 원하는 언어로 번역 할 수 있다면 시간이 다음과 같이 지배되기 때문에 이보다 훨씬 더 빨리 갈 수는 없습니다 print.
void perm(char* s, int n, int i){
if (i >= n-1) print(s);
else {
perm(s, n, i+1);
for (int j = i+1; j<n; j++){
swap(s[i], s[j]);
perm(s, n, i+1);
swap(s[i], s[j]);
}
}
}
perm("ABC", 3, 0);
내가 아는 가장 빠른 순열 알고리즘은 QuickPerm 알고리즘입니다.
구현은 다음과 같습니다. yield return을 사용하므로 필요에 따라 한 번에 하나씩 반복 할 수 있습니다.
암호:
public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
{
int N = set.Count();
int[] a = new int[N];
int[] p = new int[N];
var yieldRet = new T[N];
List<T> list = new List<T>(set);
int i, j, tmp; // Upper Index i; Lower Index j
for (i = 0; i < N; i++)
{
// initialize arrays; a[N] can be any type
a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
p[i] = 0; // p[i] == i controls iteration and index boundaries for i
}
yield return list;
//display(a, 0, 0); // remove comment to display array a[]
i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
while (i < N)
{
if (p[i] < i)
{
j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
tmp = a[j]; // swap(a[j], a[i])
a[j] = a[i];
a[i] = tmp;
//MAIN!
for (int x = 0; x < N; x++)
{
yieldRet[x] = list[a[x]-1];
}
yield return yieldRet;
//display(a, j, i); // remove comment to display target array a[]
// MAIN!
p[i]++; // increase index "weight" for i by one
i = 1; // reset index i to 1 (assumed)
}
else
{
// otherwise p[i] == i
p[i] = 0; // reset p[i] to zero
i++; // set new index value for i (increase by one)
} // if (p[i] < i)
} // while(i < N)
}
내가 끝낸 가장 빠른 구현은 다음과 같습니다.
public class Permutations
{
private readonly Mutex _mutex = new Mutex();
private Action<int[]> _action;
private Action<IntPtr> _actionUnsafe;
private unsafe int* _arr;
private IntPtr _arrIntPtr;
private unsafe int* _last;
private unsafe int* _lastPrev;
private unsafe int* _lastPrevPrev;
public int Size { get; private set; }
public bool IsRunning()
{
return this._mutex.SafeWaitHandle.IsClosed;
}
public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
{
return this.Permutate(start, count, action, null, async);
}
public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
{
return this.Permutate(start, count, null, actionUnsafe, async);
}
private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
{
if (!this._mutex.WaitOne(0))
{
return false;
}
var x = (Action)(() =>
{
this._actionUnsafe = actionUnsafe;
this._action = action;
this.Size = count;
this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
this._arrIntPtr = new IntPtr(this._arr);
for (var i = 0; i < count - 3; i++)
{
this._arr[i] = start + i;
}
this._last = this._arr + count - 1;
this._lastPrev = this._last - 1;
this._lastPrevPrev = this._lastPrev - 1;
*this._last = count - 1;
*this._lastPrev = count - 2;
*this._lastPrevPrev = count - 3;
this.Permutate(count, this._arr);
});
if (!async)
{
x();
}
else
{
new Thread(() => x()).Start();
}
return true;
}
private unsafe void Permutate(int size, int* start)
{
if (size == 3)
{
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
Swap(this._last, this._lastPrevPrev);
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
Swap(this._last, this._lastPrevPrev);
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
return;
}
var sizeDec = size - 1;
var startNext = start + 1;
var usedStarters = 0;
for (var i = 0; i < sizeDec; i++)
{
this.Permutate(sizeDec, startNext);
usedStarters |= 1 << *start;
for (var j = startNext; j <= this._last; j++)
{
var mask = 1 << *j;
if ((usedStarters & mask) != mask)
{
Swap(start, j);
break;
}
}
}
this.Permutate(sizeDec, startNext);
if (size == this.Size)
{
this._mutex.ReleaseMutex();
}
}
private unsafe void DoAction()
{
if (this._action == null)
{
if (this._actionUnsafe != null)
{
this._actionUnsafe(this._arrIntPtr);
}
return;
}
var result = new int[this.Size];
fixed (int* pt = result)
{
var limit = pt + this.Size;
var resultPtr = pt;
var arrayPtr = this._arr;
while (resultPtr < limit)
{
*resultPtr = *arrayPtr;
resultPtr++;
arrayPtr++;
}
}
this._action(result);
}
private static unsafe void Swap(int* a, int* b)
{
var tmp = *a;
*a = *b;
*b = tmp;
}
}
사용 및 테스트 성능 :
var perms = new Permutations();
var sw1 = Stopwatch.StartNew();
perms.Permutate(0,
11,
(Action<int[]>)null); // Comment this line and...
//PrintArr); // Uncomment this line, to print permutations
sw1.Stop();
Console.WriteLine(sw1.Elapsed);
인쇄 방법 :
private static void PrintArr(int[] arr)
{
Console.WriteLine(string.Join(",", arr));
}
더 자세히 알아보기 :
나는 이것에 대해 오랫동안 생각조차하지 않았기 때문에 내 코드를 너무 많이 설명 할 수 있지만 일반적인 아이디어는 다음과 같습니다.
- 순열은 사전식이 아닙니다.이를 통해 순열 간의 작업을 실제로 수행 할 수 있습니다.
- 구현은 재귀 적이며 "보기"크기가 3 일 때 복잡한 논리를 건너 뛰고 6 개의 순열 (또는 원하는 경우 하위 순열)을 얻기 위해 6 개의 스왑을 수행합니다.
- 순열이 사전 식 순서가 아니기 때문에 현재 "뷰"(하위 순열)의 시작 부분에 가져올 요소를 어떻게 결정할 수 있습니까? 현재 하위 순열 재귀 호출에서 이미 "스타터"로 사용 된 요소를 기록하고 배열의 꼬리 부분에서 사용되지 않은 요소를 선형 적으로 검색합니다.
- 구현은 정수 전용이므로 일반 요소 컬렉션에 대해 순열하려면 실제 컬렉션 대신 순열 클래스를 사용하여 인덱스를 순화하면됩니다.
- Mutex는 실행이 비동기적일 때 문제가 발생하지 않도록하기위한 것입니다 (순차 배열에 대한 포인터를 가져 오는 UnsafeAction 매개 변수를 전달할 수 있습니다. 해당 배열의 요소 순서를 변경해서는 안 됨). (포인터)! 원하는 경우 배열을 tmp 배열에 복사하거나이를 처리하는 안전한 동작 매개 변수를 사용해야합니다. 전달 된 배열은 이미 복사본입니다).
노트 :
이 구현이 실제로 얼마나 좋은지 전혀 모르겠습니다. 그렇게 오랫동안 다루지 않았습니다. 직접 다른 구현을 테스트하고 비교하고 의견이 있으면 알려주세요!
즐겨.
업데이트 2018-05-28, 새 버전, 가장 빠른 ... (멀티 스레드)
Time taken for fastest algorithms
필요 : Sani Singh Huttunen (가장 빠른 어휘) 솔루션과 인덱싱을 지원하는 새로운 OuelletLexico3
인덱싱에는 두 가지 주요 이점이 있습니다.
- 누구나 순열을 직접 얻을 수 있습니다.
- 멀티 스레딩 허용 (첫 번째 이점에서 파생 됨)
기사 : 순열 : 빠른 구현 및 멀티 스레딩을 허용하는 새로운 인덱싱 알고리즘
내 컴퓨터에서 (6 개의 하이퍼 스레드 코어 : 12 개의 스레드) Xeon E5-1660 0 @ 3.30Ghz, 13 개에 대해 수행 할 빈 작업으로 실행되는 알고리즘을 테스트합니다! 항목 (밀리 초 단위의 시간) :
- 53071 : Ouellet (힙 구현)
- 65366 : Sani Singh Huttunen (가장 빠른 어휘)
- 11377 : Mix OuelletLexico3-Sani Singh Huttunen
참고 : 순열 작업을 위해 스레드간에 공유 속성 / 변수를 사용하면 사용이 수정 (읽기 / 쓰기) 인 경우 성능에 큰 영향을 미칩니다. 그렇게하면 스레드간에 " 잘못된 공유 " 가 생성 됩니다. 예상 된 성능을 얻지 못할 것입니다. 테스트하는 동안이 동작이 발생했습니다. 내 경험은 전체 순열 수에 대해 전역 변수를 늘리려 고 할 때 문제를 보였습니다.
용법:
PermutationMixOuelletSaniSinghHuttunen.ExecuteForEachPermutationMT(
new int[] {1, 2, 3, 4},
p =>
{
Console.WriteLine($"Values: {p[0]}, {p[1]}, p[2]}, {p[3]}");
});
암호:
using System;
using System.Runtime.CompilerServices;
namespace WpfPermutations
{
public class Factorial
{
// ************************************************************************
protected static long[] FactorialTable = new long[21];
// ************************************************************************
static Factorial()
{
FactorialTable[0] = 1; // To prevent divide by 0
long f = 1;
for (int i = 1; i <= 20; i++)
{
f = f * i;
FactorialTable[i] = f;
}
}
// ************************************************************************
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static long GetFactorial(int val) // a long can only support up to 20!
{
if (val > 20)
{
throw new OverflowException($"{nameof(Factorial)} only support a factorial value <= 20");
}
return FactorialTable[val];
}
// ************************************************************************
}
}
namespace WpfPermutations
{
public class PermutationSaniSinghHuttunen
{
public static bool NextPermutation(int[] numList)
{
/*
Knuths
1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
3. Swap a[j] with a[l].
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
*/
var largestIndex = -1;
for (var i = numList.Length - 2; i >= 0; i--)
{
if (numList[i] < numList[i + 1])
{
largestIndex = i;
break;
}
}
if (largestIndex < 0) return false;
var largestIndex2 = -1;
for (var i = numList.Length - 1; i >= 0; i--)
{
if (numList[largestIndex] < numList[i])
{
largestIndex2 = i;
break;
}
}
var tmp = numList[largestIndex];
numList[largestIndex] = numList[largestIndex2];
numList[largestIndex2] = tmp;
for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--)
{
tmp = numList[i];
numList[i] = numList[j];
numList[j] = tmp;
}
return true;
}
}
}
using System;
namespace WpfPermutations
{
public class PermutationOuelletLexico3<T> // Enable indexing
{
// ************************************************************************
private T[] _sortedValues;
private bool[] _valueUsed;
public readonly long MaxIndex; // long to support 20! or less
// ************************************************************************
public PermutationOuelletLexico3(T[] sortedValues)
{
_sortedValues = sortedValues;
Result = new T[_sortedValues.Length];
_valueUsed = new bool[_sortedValues.Length];
MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
}
// ************************************************************************
public T[] Result { get; private set; }
// ************************************************************************
/// <summary>
/// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
/// </summary>
/// <param name="sortIndex"></param>
/// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
/// <returns></returns>
public void GetSortedValuesFor(long sortIndex)
{
int size = _sortedValues.Length;
if (sortIndex < 0)
{
throw new ArgumentException("sortIndex should greater or equal to 0.");
}
if (sortIndex >= MaxIndex)
{
throw new ArgumentException("sortIndex should less than factorial(the lenght of items)");
}
for (int n = 0; n < _valueUsed.Length; n++)
{
_valueUsed[n] = false;
}
long factorielLower = MaxIndex;
for (int index = 0; index < size; index++)
{
long factorielBigger = factorielLower;
factorielLower = Factorial.GetFactorial(size - index - 1); // factorielBigger / inverseIndex;
int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);
int correctedResultItemIndex = 0;
for(;;)
{
if (! _valueUsed[correctedResultItemIndex])
{
resultItemIndex--;
if (resultItemIndex < 0)
{
break;
}
}
correctedResultItemIndex++;
}
Result[index] = _sortedValues[correctedResultItemIndex];
_valueUsed[correctedResultItemIndex] = true;
}
}
// ************************************************************************
}
}
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
namespace WpfPermutations
{
public class PermutationMixOuelletSaniSinghHuttunen
{
// ************************************************************************
private long _indexFirst;
private long _indexLastExclusive;
private int[] _sortedValues;
// ************************************************************************
public PermutationMixOuelletSaniSinghHuttunen(int[] sortedValues, long indexFirst = -1, long indexLastExclusive = -1)
{
if (indexFirst == -1)
{
indexFirst = 0;
}
if (indexLastExclusive == -1)
{
indexLastExclusive = Factorial.GetFactorial(sortedValues.Length);
}
if (indexFirst >= indexLastExclusive)
{
throw new ArgumentException($"{nameof(indexFirst)} should be less than {nameof(indexLastExclusive)}");
}
_indexFirst = indexFirst;
_indexLastExclusive = indexLastExclusive;
_sortedValues = sortedValues;
}
// ************************************************************************
public void ExecuteForEachPermutation(Action<int[]> action)
{
// Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} started: {_indexFirst} {_indexLastExclusive}");
long index = _indexFirst;
PermutationOuelletLexico3<int> permutationOuellet = new PermutationOuelletLexico3<int>(_sortedValues);
permutationOuellet.GetSortedValuesFor(index);
action(permutationOuellet.Result);
index++;
int[] values = permutationOuellet.Result;
while (index < _indexLastExclusive)
{
PermutationSaniSinghHuttunen.NextPermutation(values);
action(values);
index++;
}
// Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} ended: {DateTime.Now.ToString("yyyyMMdd_HHmmss_ffffff")}");
}
// ************************************************************************
public static void ExecuteForEachPermutationMT(int[] sortedValues, Action<int[]> action)
{
int coreCount = Environment.ProcessorCount; // Hyper treading are taken into account (ex: on a 4 cores hyperthreaded = 8)
long itemsFactorial = Factorial.GetFactorial(sortedValues.Length);
long partCount = (long)Math.Ceiling((double)itemsFactorial / (double)coreCount);
long startIndex = 0;
var tasks = new List<Task>();
for (int coreIndex = 0; coreIndex < coreCount; coreIndex++)
{
long stopIndex = Math.Min(startIndex + partCount, itemsFactorial);
PermutationMixOuelletSaniSinghHuttunen mix = new PermutationMixOuelletSaniSinghHuttunen(sortedValues, startIndex, stopIndex);
Task task = Task.Run(() => mix.ExecuteForEachPermutation(action));
tasks.Add(task);
if (stopIndex == itemsFactorial)
{
break;
}
startIndex = startIndex + partCount;
}
Task.WaitAll(tasks.ToArray());
}
// ************************************************************************
}
}
다음은 컬렉션의 모든 순열을 반복하고 평가 함수를 호출하는 일반적인 순열 찾기입니다. 평가 함수가 true를 반환하면 (찾고있는 답을 찾았 음) 순열 찾기가 처리를 중지합니다.
public class PermutationFinder<T>
{
private T[] items;
private Predicate<T[]> SuccessFunc;
private bool success = false;
private int itemsCount;
public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
{
this.items = items;
this.SuccessFunc = SuccessFunc;
this.itemsCount = items.Count();
Recurse(0);
}
private void Recurse(int index)
{
T tmp;
if (index == itemsCount)
success = SuccessFunc(items);
else
{
for (int i = index; i < itemsCount; i++)
{
tmp = items[index];
items[index] = items[i];
items[i] = tmp;
Recurse(index + 1);
if (success)
break;
tmp = items[index];
items[index] = items[i];
items[i] = tmp;
}
}
}
}
다음은 간단한 구현입니다.
class Program
{
static void Main(string[] args)
{
new Program().Start();
}
void Start()
{
string[] items = new string[5];
items[0] = "A";
items[1] = "B";
items[2] = "C";
items[3] = "D";
items[4] = "E";
new PermutationFinder<string>().Evaluate(items, Evaluate);
Console.ReadLine();
}
public bool Evaluate(string[] items)
{
Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
bool someCondition = false;
if (someCondition)
return true; // Tell the permutation finder to stop.
return false;
}
}
다음은 배열 요소의 스와핑을 기반으로 하는 복잡성 O(n * n!)1 의 재귀 적 구현입니다 . 배열은의 값으로 초기화됩니다 1, 2, ..., n.
using System;
namespace Exercise
{
class Permutations
{
static void Main(string[] args)
{
int setSize = 3;
FindPermutations(setSize);
}
//-----------------------------------------------------------------------------
/* Method: FindPermutations(n) */
private static void FindPermutations(int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = i + 1;
}
int iEnd = arr.Length - 1;
Permute(arr, iEnd);
}
//-----------------------------------------------------------------------------
/* Method: Permute(arr) */
private static void Permute(int[] arr, int iEnd)
{
if (iEnd == 0)
{
PrintArray(arr);
return;
}
Permute(arr, iEnd - 1);
for (int i = 0; i < iEnd; i++)
{
swap(ref arr[i], ref arr[iEnd]);
Permute(arr, iEnd - 1);
swap(ref arr[i], ref arr[iEnd]);
}
}
}
}
각 재귀 단계에 우리는의 지역 변수가 가리키는 현재 요소의 마지막 요소를 교환 for루프 우리는에 의해 교환의 고유성 나타냅니다의 로컬 변수 증가 for루프와의 종료 조건 감소시키는 for루프를하는 처음에는 배열의 요소 수로 설정되며 후자가 0이되면 재귀를 종료합니다.
다음은 도우미 기능입니다.
//-----------------------------------------------------------------------------
/*
Method: PrintArray()
*/
private static void PrintArray(int[] arr, string label = "")
{
Console.WriteLine(label);
Console.Write("{");
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i]);
if (i < arr.Length - 1)
{
Console.Write(", ");
}
}
Console.WriteLine("}");
}
//-----------------------------------------------------------------------------
/*
Method: swap(ref int a, ref int b)
*/
private static void swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
1. 인쇄 할 요소의 n!순열이 n있습니다.
정말로 많은 개선이 발견된다면 놀랄 것입니다. 그렇다면 C #은 근본적인 개선이 필요합니다. 또한 순열을 사용하여 흥미로운 작업을 수행하면 일반적으로 생성하는 것보다 더 많은 작업이 필요합니다. 따라서 전체적인 계획에서 생성 비용은 미미할 것입니다.
즉, 다음과 같은 것을 시도해 볼 것을 제안합니다. 이미 반복기를 시도했습니다. 그러나 클로저를 입력으로 취한 다음 발견 된 각 순열에 대해 클로저를 호출하는 함수를 시도해 보셨습니까? C #의 내부 메커니즘에 따라 더 빠를 수 있습니다.
마찬가지로 특정 순열을 반복하는 클로저를 반환하는 함수를 사용해 보셨습니까?
어느 방법을 사용하든 실험 할 수있는 여러 가지 마이크로 최적화가 있습니다. 예를 들어 입력 배열을 정렬 할 수 있으며 그 후에는 항상 어떤 순서인지 알 수 있습니다. 예를 들어 해당 요소가 다음 요소보다 작은 지 여부를 나타내는 bool 배열을 가질 수 있으며 비교를 수행하는 대신 다음을 수행 할 수 있습니다. 저 배열을보세요.
Steven Skiena의 Algorithm Design Manual (제 2 판 14.4 장) 에는 알고리즘에 대한 접근 가능한 소개 및 구현 조사가 있습니다.
Skiena는 D. Knuth를 참조합니다. The Art of Computer Programming, Volume 4 Fascicle 2 : Generating All Tuples and Permutations. 애디슨 웨슬리, 2005.
Knuth의 알고리즘보다 약간 빠르게 알고리즘을 만들었습니다.
11 가지 요소 :
내 : 0.39 초
Knuth : 0.624 초
13 가지 요소 :
내 : 56.615 초
Knuth : 98.681 초
Java로 작성된 코드는 다음과 같습니다.
public static void main(String[] args)
{
int n=11;
int a,b,c,i,tmp;
int end=(int)Math.floor(n/2);
int[][] pos = new int[end+1][2];
int[] perm = new int[n];
for(i=0;i<n;i++) perm[i]=i;
while(true)
{
//this is where you can use the permutations (perm)
i=0;
c=n;
while(pos[i][1]==c-2 && pos[i][0]==c-1)
{
pos[i][0]=0;
pos[i][1]=0;
i++;
c-=2;
}
if(i==end) System.exit(0);
a=(pos[i][0]+1)%c+i;
b=pos[i][0]+i;
tmp=perm[b];
perm[b]=perm[a];
perm[a]=tmp;
if(pos[i][0]==c-1)
{
pos[i][0]=0;
pos[i][1]++;
}
else
{
pos[i][0]++;
}
}
}
문제는 내 알고리즘이 홀수 요소에서만 작동한다는 것입니다. 이 코드를 빨리 작성 했으므로 더 나은 성능을 얻기 위해 내 아이디어를 구현하는 더 좋은 방법이 있다고 확신합니다.하지만 지금은이를 최적화하고 문제를 해결하기 위해 작업 할 시간이 없습니다. 요소는 짝수입니다.
모든 순열에 대해 한 번의 교체이며 교체 할 요소를 아는 매우 간단한 방법을 사용합니다.
내 블로그에 코드 뒤에있는 방법에 대한 설명을 썼습니다. http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html
이 질문의 저자는 알고리즘에 대해 질문했습니다.
[...] 한 번에 하나의 순열을 생성하고 필요한 경우에만 계속
나는 Steinhaus-Johnson-Trotter 알고리즘을 고려할 것을 제안합니다.
Wikipedia의 Steinhaus–Johnson–Trotter 알고리즘
여기에 아름답게 설명
오전 1시이고 TV를보고 있었는데이 같은 질문을 생각했지만 문자열 값이 있습니다.
단어가 주어지면 모든 순열을 찾으십시오. 배열, 세트 등을 처리하기 위해 쉽게 수정할 수 있습니다.
그것을 해결하기 위해 약간의 시간이 필요했지만 내가 찾은 해결책은 다음과 같습니다.
string word = "abcd";
List<string> combinations = new List<string>();
for(int i=0; i<word.Length; i++)
{
for (int j = 0; j < word.Length; j++)
{
if (i < j)
combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
else if (i > j)
{
if(i== word.Length -1)
combinations.Add(word[i] + word.Substring(0, i));
else
combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));
}
}
}
다음은 위와 동일한 코드이지만 몇 가지 주석이 있습니다.
string word = "abcd";
List<string> combinations = new List<string>();
//i is the first letter of the new word combination
for(int i=0; i<word.Length; i++)
{
for (int j = 0; j < word.Length; j++)
{
//add the first letter of the word, j is past i so we can get all the letters from j to the end
//then add all the letters from the front to i, then skip over i (since we already added that as the beginning of the word)
//and get the remaining letters from i+1 to right before j.
if (i < j)
combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
else if (i > j)
{
//if we're at the very last word no need to get the letters after i
if(i== word.Length -1)
combinations.Add(word[i] + word.Substring(0, i));
//add i as the first letter of the word, then get all the letters up to i, skip i, and then add all the lettes after i
else
combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));
}
}
}
나는 rosetta 코드에서이 알고리즘을 발견했고 내가 시도한 것 중 가장 빠른 것이다. http://rosettacode.org/wiki/Permutations#C
/* Boothroyd method; exactly N! swaps, about as fast as it gets */
void boothroyd(int *x, int n, int nn, int callback(int *, int))
{
int c = 0, i, t;
while (1) {
if (n > 2) boothroyd(x, n - 1, nn, callback);
if (c >= n - 1) return;
i = (n & 1) ? 0 : c;
c++;
t = x[n - 1], x[n - 1] = x[i], x[i] = t;
if (callback) callback(x, nn);
}
}
/* entry for Boothroyd method */
void perm2(int *x, int n, int callback(int*, int))
{
if (callback) callback(x, n);
boothroyd(x, n, n, callback);
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/**
* http://marknelson.us/2002/03/01/next-permutation/
* Rearranges the elements into the lexicographically next greater permutation and returns true.
* When there are no more greater permutations left, the function eventually returns false.
*/
// next lexicographical permutation
template <typename T>
bool next_permutation(T &arr[], int firstIndex, int lastIndex)
{
int i = lastIndex;
while (i > firstIndex)
{
int ii = i--;
T curr = arr[i];
if (curr < arr[ii])
{
int j = lastIndex;
while (arr[j] <= curr) j--;
Swap(arr[i], arr[j]);
while (ii < lastIndex)
Swap(arr[ii++], arr[lastIndex--]);
return true;
}
}
return false;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
/**
* Swaps two variables or two array elements.
* using references/pointers to speed up swapping.
*/
template<typename T>
void Swap(T &var1, T &var2)
{
T temp;
temp = var1;
var1 = var2;
var2 = temp;
}
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
// driver program to test above function
#define N 3
void OnStart()
{
int i, x[N];
for (i = 0; i < N; i++) x[i] = i + 1;
printf("The %i! possible permutations with %i elements:", N, N);
do
{
printf("%s", ArrayToString(x));
} while (next_permutation(x, 0, N - 1));
}
// Output:
// The 3! possible permutations with 3 elements:
// "1,2,3"
// "1,3,2"
// "2,1,3"
// "2,3,1"
// "3,1,2"
// "3,2,1"// Permutations are the different ordered arrangements of an n-element
// array. An n-element array has exactly n! full-length permutations.
// This iterator object allows to iterate all full length permutations
// one by one of an array of n distinct elements.
// The iterator changes the given array in-place.
// Permutations('ABCD') => ABCD DBAC ACDB DCBA
// BACD BDAC CADB CDBA
// CABD ADBC DACB BDCA
// ACBD DABC ADCB DBCA
// BCAD BADC CDAB CBDA
// CBAD ABDC DCAB BCDA
// count of permutations = n!
// Heap's algorithm (Single swap per permutation)
// http://www.quickperm.org/quickperm.php
// https://stackoverflow.com/a/36634935/4208440
// https://en.wikipedia.org/wiki/Heap%27s_algorithm
// My implementation of Heap's algorithm:
template<typename T>
class PermutationsIterator
{
int b, e, n;
int c[32]; /* control array: mixed radix number in rising factorial base.
the i-th digit has base i, which means that the digit must be
strictly less than i. The first digit is always 0, the second
can be 0 or 1, the third 0, 1 or 2, and so on.
ArrayResize isn't strictly necessary, int c[32] would suffice
for most practical purposes. Also, it is much faster */
public:
PermutationsIterator(T &arr[], int firstIndex, int lastIndex)
{
this.b = firstIndex; // v.begin()
this.e = lastIndex; // v.end()
this.n = e - b + 1;
ArrayInitialize(c, 0);
}
// Rearranges the input array into the next permutation and returns true.
// When there are no more permutations left, the function returns false.
bool next(T &arr[])
{
// find index to update
int i = 1;
// reset all the previous indices that reached the maximum possible values
while (c[i] == i)
{
c[i] = 0;
++i;
}
// no more permutations left
if (i == n)
return false;
// generate next permutation
int j = (i & 1) == 1 ? c[i] : 0; // IF i is odd then j = c[i] otherwise j = 0.
swap(arr[b + j], arr[b + i]); // generate a new permutation from previous permutation using a single swap
// Increment that index
++c[i];
return true;
}
};가능한 순열 수를 계산하려는 경우 위의 모든 노력을 피하고 다음과 같은 것을 사용할 수 있습니다 (c #에서 고려 됨).
public static class ContrivedUtils
{
public static Int64 Permutations(char[] array)
{
if (null == array || array.Length == 0) return 0;
Int64 permutations = array.Length;
for (var pos = permutations; pos > 1; pos--)
permutations *= pos - 1;
return permutations;
}
}
다음과 같이 부릅니다.
var permutations = ContrivedUtils.Permutations("1234".ToCharArray());
// output is: 24
var permutations = ContrivedUtils.Permutations("123456789".ToCharArray());
// output is: 362880
참조 URL : https://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently
반응형
'code' 카테고리의 다른 글
| Vim의 탭 및 백 스페이스 동작으로서의 공백 (0) | 2020.12.25 |
|---|---|
| Entity Framework 코드 첫 번째 AddOrUpdate 메서드 삽입 중복 값 (0) | 2020.12.25 |
| 왜`int;`는 C에서는 잘 컴파일되지만 C ++에서는 컴파일되지 않습니까? (0) | 2020.12.24 |
| 연결할 수없는 코드가 잘 작동합니다.-어떻게? (0) | 2020.12.24 |
| jQuery는 "선택자"의 캐싱을 수행합니까? (0) | 2020.12.24 |