Уникальные перестановки без зеркальных или круговых повторений

Question

Краткая справка: я пишу более или менее грубый алгоритм поиска для решения проблемы, которая у меня есть. Для этого мне нужно сгенерировать и оценить все возможности, чтобы выяснить, какая из них лучше. Поскольку оценка на самом деле занимает некоторое время, я бы предпочел генерировать как можно меньше решений, которые полностью покрывают мое пространство поиска. Кроме того, чем больше элементов я могу сделать, тем лучше. Для любого числа K обычно есть K! перестановки, и генерация их всех будет трудно для чисел выше ~ 10.

Реальная проблема: пространство поиска должно содержать все перестановки двух элементов (N раз el1 и M раз el2, где K = M + N) со следующими ограничениями:

1. они должны быть уникальными (т.е. я хочу только [a a b b b] один раз)
2. Мне не нужна обратная перестановка (т. Е. Если у меня есть [a a b], мне также не нужно [b a a])
3. Я считаю перестановки круговыми, поэтому [a a b] = [a b a] = [b a a]

Если бы я мог сделать это, число возможностей было бы резко уменьшено. Поскольку K в идеале будет большим, не представляется возможным сначала генерировать все перестановки, а затем фильтровать их в соответствии с этими критериями. Я уже сделал первое ограничение (см. Ниже), и оно сократило число с 2 ^ K для функции нормальных перестановок Матлаба (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]. Вычтите это усиление из длины перестановки, и вы получите индекс, с которого вы можете начинать вставку новых элементов без создания дубликатов.

Answer 1

То, что вам нужно, это подмножество 2-х браслетов (подмножество определяется ровно n символа A и m символа B). Набор браслетов all позволяет варьировать количество 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;
}

Answer 2

Я думаю, вы хотите создать 2-х бесплатных ожерелий. См. этот вопрос для ссылки, документов и некоторого кода.

Answer 3

Вы ищете комбинации - которые не зависят от заказа. Матлаб рассчитал это правильно с K! / N! M! это точно формула для расчета количества комбинаций.

Answer 4

Предполагая, что у вас есть массив всех перестановок, вы можете поместить содержимое массива в хеш. Тогда это будет работать (немного грубой силы, но это начало):

for each (element in array of permutations){
  if (element exists in hash){
    remove each circular permutation of element in hash except for element itself
  }
}

Answer 5

Если у вас есть только два элемента, ваше пространство намного меньше: 2 ^ k, а не k!.

Попробуйте такой подход:

1. Пробежать все числа от 1 до 2 ^ k.
2. Введите число в двоичном виде.
3. Переведите все 0 в a и 1 в b. Теперь у вас есть перестановка.
4. Возьмите вашу последовательность и сгенерируйте 2k последовательностей путем циклических перестановок и обращения. Вам нужно только оценить 1 из этих 2k последовательностей.
5. Среди последовательностей 2k выберите ту, которая сортирует сначала по алфавиту.
6. Проверьте ваш журнал, чтобы увидеть, если вы уже сделали это. Если это так, пропустите.
7. Если он новый, оцените его и добавьте в журнал «готово». (Если пространство позволяет, вы можете добавить все 2k элементов "семейства" в журнал готовых операций, чтобы вы могли переместить шаг (6) сразу после шага (3). Вы также можете сохранить число, а не последовательность и б, в "готовом" журнале.)

Если у вас есть j возможных символов, а не только два, сделайте то же самое, но используйте базу j вместо базы 2.