Уникальные перестановки без зеркальных или круговых повторений
https://stackoverflow.com/questions/1137439
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Некоторые предыстории: я пишу более или менее грубый алгоритм поиска силы для решения проблемы, с которой у меня есть. Чтобы сделать это, мне нужно генерировать и оценить все возможности, чтобы выяснить, что лучше. Поскольку оценка фактически занимает некоторое время, я бы предпочел генерировать как можно меньше решений, которые полностью охватывают мое пространство поиска. Кроме того, чем больше элементов я могу это сделать, тем лучше. Для любого номера K обычно k! перестановки и их генерирование будет трудно для чисел выше ~ 10.
Реальная проблема: пространство поиска должно содержать все перестановки двух элементов (n Times el1 и m times el2, где k = m+n), с этими ограничениями:
- Они должны быть уникальными (т.е. я хочу [aabbb] только один раз)
- Мне не нужна обратная перестановка (то есть, если у меня есть [AAB], мне также не нужно [BAA])
- Я считаю перестановку круговыми, поэтому [aab] = [aba] = [baa
Если бы я смог сделать это, количество возможностей было бы резко уменьшено. Поскольку K в идеале будет большим, невозможно сначала генерировать все перестановки, а затем фильтровать их в соответствии с этими критериями. Я уже сделал первое ограничение (см. Ниже), и оно сократило число от 2^K для обычной функции перестановки Matlab (Perms) до 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, то вы можете использовать их, чтобы найти перестановки для N и M, вставив в них E1. Вы не можете просто вставить везде, потому что тогда вы получите дубликаты. Я не знаю, почему это работает, но вы можете рассчитать количество новых возможностей, которые вы генерируете от старого (я называю это «усилением»). Это число начинается с M+1 для первой старой перестановки и уменьшается по одному для каждой старой перестановки, пока оно не станет нулевым, после чего оно вернется к M и т. Д. (только работает, если M> = n). Поэтому, если вы хотите рассчитать перестановки для n = 3 и m = 3, и у вас есть 10 перестановки на n = 2 и m = 3, их прибыль будет [4 3 2 1 3 2 1 2 1 1]. Вычтите эту выгоду от длины перестановки, и вы получаете индекс, при котором вы можете начать вставлять новые элементы, не делая дубликатов.
Решение
То, что вы хотите,-это подмножество 2-х браслетов (подмножество определяется точно n символом A и M символа B). Набор все Браслеты позволяют различаться количество A и B.
Следующий код распечатывает последовательности, которые вы хотите, и делает это в лексическом порядке и в постоянное амортизированное время. Он основан на общем алгоритме в Эта статья Савада - Для объяснения того, как это работает, см. Эта статья.
#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
}
}
Если у вас есть только два элемента, ваше пространство намного меньше: 2^k, а не K!.
Попробуйте такой подход, как это:
- Пропустить все числа от 1 до 2^k.
- Напишите номер в двоичной форме.
- Переведите все 0 с. И 1 на б. Теперь у вас есть перестановка.
- Возьмите свою последовательность и генерируйте 2K -последовательности с помощью циклических перестановков и отмены. Вам нужно оценить только 1 из этих 2K -последовательностей.
- Среди 2K -последовательностей выберите тот, который сначала сортирует в алфавитном порядке.
- Проверьте свой журнал, чтобы увидеть, если вы уже сделали это. Если так, пропустите.
- Если этот новый, оцените его и добавьте в журнал «DED». (Если позволит пространство, вы можете добавить все 2K -элементы «семьи» в журнал выполненного и б, в журнале «Готово».)
Если у вас есть возможные символы, а не только два, сделайте то же самое, но используйте базовую j, а не базу 2.
