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

Запишите, какие символы вы поменяли местами ранее:

 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

В стандартной библиотеке есть то, что вам нужно:

#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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

EDIT: Кто-нибудь пробовал это? Есть ли более простое или быстрое решение? Это разочаровывает, что никто не прокомментировал дальше!

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

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

В Питоне:

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]

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

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

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