Перестановка строковых букв: как убрать повторные перестановки?

Question

Вот стандартная функция для печати перестановок символов строки:

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j < n; j++) //check till end of string
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

Работает нормально, но есть проблема, он также печатает несколько повторяющихся перестановок, например:

если строка "AAB"

вывод:

AAB
ABA
AAB
ABA
BAA
BAA

Здесь также есть 3 повторяющиеся записи.

Может ли быть способ предотвратить это?

-

Спасибо

Алок Кр.

Answer 1

Делайте заметки, какие символы вы поменяли местами ранее:

 char was[256];
 /*
 for(j = 0; j <= 255; j++)
    was[j] = 0;
 */
 bzero(was, 256);
 for (j = i; j <= n; j++)
 {
    if (!was[*(a+j)]) {
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
      was[*(a+j)] = 1;
    }
 }

Это должен быть самый быстрый из пока что входов, некоторые тесты для AAAABBBCCD (100 циклов):

native C             - real    0m0.547s
STL next_permutation - real    0m2.141s

Answer 2

Другой подход может быть следующим:

1. Предварительная сортировка массива.

2. Это гарантирует, что все дубликаты теперь будут последовательными.

3. Итак, нам просто нужно увидеть предыдущий элемент, который мы исправили (и переставили другие)

4. если текущий элемент такой же, как предыдущий, неперестановка.

Answer 3

Стандартная библиотека имеет то, что вам нужно:

#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
using namespace std;

void print_all_permutations(const string& s)
{
    string s1 = s;
    sort(s1.begin(), s1.end()); 
    do {
        cout << s1 << endl;
    } while (next_permutation(s1.begin(), s1.end()));
}

int main()
{
    print_all_permutations("AAB");
}

Результат:

$ ./a.out
AAB
ABA
BAA

Answer 4

Вы можете использовать std::set для обеспечения уникальности результатов.То есть, если это C ++ (потому что вы пометили его как таковой).

В противном случае - просмотрите список результатов вручную и удалите дубликаты.конечно, постобработать их, а не печатать сразу, как сейчас.

Answer 5

Я бы сделал это следующим образом: во-первых, я генерирую «группы» символов (т. Е. AABBBC дает две группы: (AA) and (BBB) and (C).

Сначала мы перебираем все распределения AA на символы n. Для каждого найденного распределения мы перебираем все распределения BBB на n-2 оставшихся символов (не занятых A). Для каждого из этих распределений, включающих A s и B s, мы повторяем все распределения C по оставшимся свободным позициям символов.

Answer 6

Это было бы довольно просто, если вы просто считаете это проблемой, когда вам нужно хранить все перестановки для будущего использования.

ТАК, что у вас будет массив переставленных строк.

Теперь подумайте о новой проблеме, которая также является стандартной, в которой вам нужно удалить дубликаты из массива.

Надеюсь, это поможет.

Answer 7

Не переставлять для одного и того же символа в другой позиции string.

В Python:

def unique_permutation(a, l, r):
    if l == r:
        print ''.join(a)
        return
    for i in range(l, r+1):
        if i != l and a[i] == a[l]:
            continue
        a[i], a[l] = a[l], a[i]
        unique_permutation(a, l+1, r)
        a[i], a[l] = a[l], a[i]

Answer 8

Шаг алгоритма:

1. Сохранить данную строку во временную строку, скажем "temp"
2. Удалить дубликаты из временной строки
3. И, наконец, вызов функции «void permute (char * a, int i, int n)» для вывода всех перестановок данной строки без дубликатов

Я думаю, это лучшее и эффективное решение.

Answer 9

void permute(string set, string prefix = ""){
    if(set.length() == 1){
            cout<<"\n"<<prefix<<set;
    }
    else{
            for(int i=0; i<set.length(); i++){
                    string new_prefix = prefix;
                    new_prefix.append(&set[i], 1);
                    string new_set = set;
                    new_set.erase(i, 1);
                    permute(new_set, new_prefix);
            }
    }
}

И просто используйте его как перестановку ("слово");

Answer 10

@ Кумар, я думаю, что ты хочешь что-то вроде следующего:

#include <stdio.h>
#include <string.h>

/* print all unique permutations of some text. */
void permute(int offset, int* offsets, const char* text, int text_size)
{
    int i;

    if (offset < text_size) {
            char c;
            int j;

            /* iterate over all possible digit offsets. */
            for (i=0; i < text_size; i++) {
                    c=text[i];
                    /* ignore if an offset further left points to our
                       location or to the right, with an identical digit.
                       This avoids duplicates. */
                    for (j=0; j < offset; j++) {
                            if ((offsets[j] >= i) &&
                                (text[offsets[j]] == c)) {
                                    break;
                            }
                    }

                    /* nothing found. */
                    if (j == offset) {
                            /* remember current offset. */
                            offsets[offset]=i;
                            /* permute remaining text. */
                            permute(offset+1, offsets, text, text_size);
                    }
            }
    } else {
            /* print current permutation. */
            for (i=0; i < text_size; i++) {
                    fputc(text[offsets[i]], stdout);
            }
            fputc('\n', stdout);
    }
}

int main(int argc, char* argv[])
{
    int i, offsets[1024];

    /* print permutations of all arguments. */
    for (i=1; i < argc; i++) {
            permute(0, offsets, argv[i], strlen(argv[i]));
    }

    return 0;
}

Этот код - C, как и требовалось, он довольно быстрый и делает то, что вы хотите. Конечно, он содержит возможное переполнение буфера, потому что буфер смещения имеет фиксированный размер, но это только пример, верно?

РЕДАКТИРОВАТЬ: Кто-нибудь пробовал это? Есть ли более простое или быстрое решение? К сожалению, никто не прокомментировал дальше!