Вопрос по c++, c, algorithm, permutation – Генерация подпоследовательностей

3

У меня есть строка типа «0189», для которой мне нужно сгенерировать все подпоследовательности, но порядок отдельных символов должен быть сохранен, т. Е. Здесь 9 не должно предшествовать 0, 1 или 8. Пример: 0, 018, 01, 09, 0189, 18, 19, 019 и т. Д.

Другим примером является "10292" для которых подпоследовательности будут: 1, 10, 02, 02, 09, 29, 92 и т. д. Как вы могли заметить, «02»; два раза, начиная с '2' приходит дважды в данной строке. Но опять же, такие вещи, как: 21, 01, 91 являются недействительными, так как порядок должен поддерживаться.

Любой алгоритм или псевдо-код, который может быть реализован на C / C ++, будет принят!

Каким он должен быть: C или C ++? Konrad Rudolph
Котенок умирает каждый раз, когда кто-то говорит «C / C ++». Philip
Поскольку он запрашивает алгоритмы или псевдокод C / C ++. значение C или C ++ достаточно разумно. john
Порядок сортировки относится к отдельным символам, которые, я думаю, то есть «01». в порядке, но '10' не является. john
порядок сортировки неясен в OP, 018 до 01? bph

Ваш Ответ

4   ответа
1

In [29]: def subseq(s): return ' '.join((' '.join(''.join(x) for x in combs(s,n)) for n in range(1, len(s)+1)))

In [30]: subseq("0189")
Out[30]: '0 1 8 9 01 08 09 18 19 89 018 019 089 189 0189'

In [31]: subseq("10292")
Out[31]: '1 0 2 9 2 10 12 19 12 02 09 02 29 22 92 102 109 102 129 122 192 029 022 092 292 1029 1022 1092 1292 0292 10292'

In [32]: 
0
__author__ = 'Robert'
from itertools import combinations

g = combinations(range(4), r=2)
print(list(g)) #[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

def solve(string_):
    n = len(string_)
    for repeat in range(1, len(string_) + 1):
        combos = combinations(range(len(string_)), r=repeat)
        for combo in combos:
            sub_string = "".join(string_[i] for i in combo)
            yield sub_string

print(list(solve('0189'))) #['0', '1', '8', '9', '01', '08', '09', '18', '19', '89', '018', '019', '089', '189']


#using recursion

def solve2(string_, i):
    if i >= len(string_):
        return [""] #no sub_strings beyond length of string_
    character_i = string_[i]
    all_sub_strings = solve2(string_, i + 1)
    all_sub_strings += [character_i + sub_string for sub_string in all_sub_strings]
    return all_sub_strings


print(solve2('0189', 0)) #['', '9', '8', '89', '1', '19', '18', '189', '0', '09', '08', '089', '01', '019', '018', '0189']
8

the set of subsequences can be split into the ones containing the first character and the ones not containing it the ones containing the first character are build by appending that character to the subsequences which don't contain it (+ the subsequence which contains only the first character itself)
6

power set последовательности и набора двоичных чисел из0 в2^n - 1, гдеn длина последовательности.

В твоем случае,n 4, поэтому рассмотрим 0 =0000 .. 15 = 1111; где есть1 в двоичное выражение включите соответствующий элемент из последовательности. Чтобы реализовать это, вам понадобятся битовые сдвиги и двоичные операции:

for (int i = 0; i < (1 << n); ++i) {
    std::string item;
    for (j = 0; j < n; ++j) {
        if (i & (1 << j)) {
            item += sequence[j];
        }
    }
    result.push_back(item);
}

Также подумайте, как вы обрабатываете последовательности дольше, чем может быть покрытоint (подсказка: рассмотрите переполнение и арифметический перенос).

+1 потому что ты меня побил
В этом случае было бы целесообразно рекурсивное (или рекурсивное) решение.
это сгенерирует все подпоследовательности. Что делать, если нужно генерировать подпоследовательности UPTO определенной длины (скажем, 4 = & gt; subseq длины 4,3,2,1). kunal18

Похожие вопросы