대칭 또는 순환 반복이 없는 고유한 순열
https://stackoverflow.com/questions/1137439
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
일부 배경:나는 내가 가진 문제를 해결하기 위해 다소 무차별적인 검색 알고리즘을 작성하고 있습니다.이를 위해서는 무엇이 최선인지 알아내기 위해 모든 가능성을 생성하고 평가해야 합니다.평가에는 실제로 시간이 좀 걸리기 때문에 검색 공간을 완전히 포괄하는 솔루션을 가능한 한 적게 생성하는 것을 선호합니다.게다가 내가 할 수 있는 요소가 많을수록 더 좋습니다.숫자 K에는 일반적으로 K가 있습니다!순열을 생성하고 이를 모두 생성하는 것은 ~10보다 큰 숫자에 대해서는 어려울 것입니다.
진짜 문제:검색 공간에는 두 요소의 모든 순열(N x el1 및 M x el2, 여기서 K=M+N)이 포함되어야 하며 다음 제한 사항이 적용됩니다.
- 고유해야 합니다(예:나는 [a a b b b] 한 번만 원합니다)
- 순열의 역순은 필요하지 않습니다(예:[a a b]가 있으면 [b a a]도 필요하지 않습니다.)
- 나는 순열을 원형이라고 생각하므로 [a a b] = [a b a] = [b a a]
이렇게 할 수 있다면 가능성의 수가 급격히 줄어들 것입니다.K는 이상적으로 크므로 먼저 모든 순열을 생성한 다음 이러한 기준에 따라 필터링하는 것은 불가능합니다.나는 이미 첫 번째 제한(아래 참조)을 수행했으며 Matlab의 일반 순열 함수(perms)에 대한 2^K에서 K!/N!M!으로 숫자를 줄였습니다. 이는 큰 승리입니다.두 번째 제한은 (최상의 경우) 가능성의 수를 절반으로만 줄이지만, 세 번째 제한도 실제로 가능성의 수를 줄일 수 있어야 한다고 생각합니다.
누군가 그것을 수행하는 방법을 알고 있고 가능한 한 얼마나 많은 가능성이 있는지 계산하는 방법을 알고 있다면 그것은 나에게 많은 도움이 될 것입니다!설명을 더 선호하지만 코드도 괜찮습니다(C와 유사한 언어, Java(Script), Python, Ruby, Lisp/Scheme을 읽을 수 있음).
관심 있는 분들을 위해:지금까지 가지고 있는 고유한 순열만 가져오는 알고리즘은 다음과 같습니다.
function genPossibilities(n, m, e1, e2)
if n == 0
return array of m e2's
else
possibilities = genPossibilities(n-1, m, e1, e2)
for every possibility:
gain = number of new possibilities we'll get for this smaller possibility*
for i in max(0,(m+n-gain))
if possibility(i) is not e1
add possiblity with e1 inserted in position i
return new possibilities
- N-1과 M에 대한 모든 순열이 있는 경우 e1을 삽입하여 N과 M에 대한 순열을 찾는 데 사용할 수 있습니다.하지만 아무 곳에나 삽입할 수는 없습니다. 그렇게 하면 중복 항목이 생기기 때문입니다.이것이 왜 작동하는지 모르겠지만 이전 가능성에서 생성할 새로운 가능성의 수를 계산할 수 있습니다(저는 이것을 '이득'이라고 부릅니다).이 숫자는 첫 번째 이전 순열에 대해 M+1에서 시작하여 0이 될 때까지 각 이전 순열에 대해 1씩 감소하고, 그 지점에서 다시 M으로 돌아갑니다.(M>=N인 경우에만 작동합니다).따라서 N=3 및 M=3에 대한 순열을 계산하고 N=2 및 M=3에 대한 10개의 순열이 있는 경우 해당 이득은 [4 3 2 1 3 2 1 2 1 1]입니다.순열의 길이에서 이 이득을 빼면 중복을 만들지 않고 새 요소 삽입을 시작할 수 있는 인덱스를 얻을 수 있습니다.
해결책
당신이 뒤 따르는 것은 2- 아리 팔찌의 하위 집합입니다 (서브 세트는 문자 b의 정확히 n과 m에 의해 정의됩니다). 세트 모두 팔찌를 사용하면 A와 B의 수가 다양합니다.
다음 코드는 당신이 후에있는 시퀀스를 인쇄하고 어휘 순서와 일정한 상각 시간으로 그렇게합니다. 일반 알고리즘을 기반으로합니다 이 논문은 Sawada 의이 논문 - 작동 방식에 대한 설명은 해당 논문을 참조하십시오.
#include <stdlib.h>
#include <stdio.h>
static int *a;
static int n;
void print_bracelet(int n, int a[])
{
int i;
printf("[");
for (i = 0; i < n; i++)
printf(" %c", 'a' + a[i]);
printf(" ]\n");
}
int check_rev(int t, int i)
{
int j;
for (j = i+1; j <= (t + 1)/2; j++)
{
if (a[j] < a[t-j+1])
return 0;
if (a[j] > a[t-j+1])
return -1;
}
return 1;
}
void gen_bracelets(int n_a, int n_b, int t, int p, int r, int u, int v, int rs)
{
if (2 * (t - 1) > (n + r))
{
if (a[t-1] > a[n-t+2+r])
rs = 0;
else if (a[t-1] < a[n-t+2+r])
rs = 1;
}
if (t > n)
{
if (!rs && (n % p) == 0)
print_bracelet(n, a + 1);
}
else
{
int n_a2 = n_a;
int n_b2 = n_b;
a[t] = a[t-p];
if (a[t] == 0)
n_a2--;
else
n_b2--;
if (a[t] == a[1])
v++;
else
v = 0;
if ((u == (t - 1)) && (a[t-1] == a[1]))
u++;
if ((n_a2 >= 0) && (n_b2 >= 0) && !((t == n) && (u != n) && (a[n] == a[1])))
{
if (u == v) {
int rev = check_rev(t, u);
if (rev == 0)
gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);
if (rev == 1)
gen_bracelets(n_a2, n_b2, t + 1, p, t, u, v, 0);
}
else
gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);
}
if (u == t)
u--;
if (a[t-p] == 0 && n_b > 0)
{
a[t] = 1;
if (t == 1)
gen_bracelets(n_a, n_b - 1, t + 1, t, 1, 1, 1, rs);
else
gen_bracelets(n_a, n_b - 1, t + 1, t, r, u, 0, rs);
}
}
}
int main(int argc, char *argv[])
{
int n_a, n_b;
if (argc < 3)
{
fprintf(stderr, "Usage: %s <a> <b>\n", argv[0]);
return -2;
}
n_a = atoi(argv[1]);
n_b = atoi(argv[2]);
if (n_a < 0 || n_b < 0)
{
fprintf(stderr, "a and b must be nonnegative\n");
return -3;
}
n = n_a + n_b;
a = malloc((n + 1) * sizeof(int));
if (!a)
{
fprintf(stderr, "could not allocate array\n");
return -1;
}
a[0] = 0;
gen_bracelets(n_a, n_b, 1, 1, 0, 0, 0, 0);
free(a);
return 0;
}
다른 팁
나는 당신이 2 개의 무료 목걸이를 생성하고 싶다고 생각합니다. 보다 이 질문 링크, 논문 및 일부 코드.
당신은 주문 독립적 인 조합을 찾고 있습니다. Matlab은 이것을 K!/n! m으로 올바르게 계산했습니다! 이것은 정확히 조합 수를 계산하기위한 공식입니다.
모든 순열 배열이 있다고 가정하면 배열의 내용을 해시에 넣을 수 있습니다. 그러면 이것은 작동합니다 (약간의 무자비한 힘이지만 시작) :
for each (element in array of permutations){
if (element exists in hash){
remove each circular permutation of element in hash except for element itself
}
}
요소가 두 개만 있으면 공간이 훨씬 작아집니다.k 대신 2^k!.
다음과 같은 접근 방식을 시도해 보세요.
- 1부터 2^k까지의 모든 숫자를 살펴보세요.
- 숫자를 이진 형식으로 쓰세요.
- 모든 0을 a로, 1을 b로 변환합니다.이제 순열이 생겼습니다.
- 시퀀스를 가져와 순환 순열 및 반전을 통해 2k 시퀀스를 생성합니다.이러한 2k 시퀀스 중 1개만 평가하면 됩니다.
- 2k 시퀀스 중에서 알파벳순으로 먼저 정렬되는 시퀀스를 선택합니다.
- 로그를 확인하여 이미 이 작업을 수행했는지 확인하세요.그렇다면 건너뛰세요.
- 이것이 새로운 것이라면 평가하고 "완료" 로그에 추가하십시오.(공간이 허락한다면 "패밀리"의 2k개 요소를 모두 완료 로그에 추가할 수 있으므로 단계 (6)을 단계 (3) 바로 다음으로 이동할 수 있습니다.a와 b의 순서 대신 숫자를 "완료" 로그에 저장할 수도 있습니다.)
두 개가 아닌 j개의 가능한 기호가 있는 경우 동일한 작업을 수행하되 기본 2 대신 기본 j를 사용하세요.
