Перестановка строковых букв: как удалить повторяющиеся перестановки?

Ответ 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

Ответ 2

Другим подходом может быть:

• Предварительно настройте массив.

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

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

• если текущий элемент аналогичен предыдущему, не переставляйте.

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

#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

Ответ 6

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

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

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

Я надеюсь, что это поможет.

Ответ 7

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

#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, как и было запрошено, довольно быстро и делает то, что вы хотите. Конечно, он содержит возможное переполнение буфера, потому что буфер смещения имеет фиксированный размер, но это всего лишь пример, правильно?

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

Ответ 8

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);
            }
    }
}

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

Ответ 9

Не переставляйте для одного символа в другом положении 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]

Ответ 10

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

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

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