7.2 Урок №30. Генерация последовательностей

Question

7.2 Урок №30. Генерация последовательностей

Garik Harlamov Ученик (1), закрыт 1 год назад

Напишите программу, которая во всех возможных последовательностях длиной четыре, составленных из пяти различных букв, находит позицию заданной. На вход программы в первой строке подаётся набор из пяти различных заглавных латинских букв, в алфавитном порядке. Во второй строке вводится искомая цепочка символов. Программа должна вывести номер этой цепочки, если считать, что все последовательности расположены в лексикографическом (алфавитном) порядке. Последовательности пронумерованы, начиная с 1.

Sample Input 1:

ABCDE
CABD

Sample Output 1:

259

Sample Input 2:

RSTWZ
ZWSR

Sample Output 2:

581

Answer 1

 #include  
#include  
#include  
#include  
 
using namespace std; 
 
vector generateCombinations(string letters, int n) { 
    vector combinations; 
    string combination(n, ' '); 
 
    function backtrack = [&](int k) { 
        if (k == n) { 
            combinations.push_back(combination); 
            return; 
        } 
        for (char c : letters) { 
            combination[k] = c; 
            backtrack(k + 1); 
        } 
    }; 
    backtrack(0); 
    return combinations; 
} 
 
int main() { 
    string letters; 
    cin >> letters; 
 
    string sequence; 
    cin >> sequence; 
 
    vector comb = generateCombinations(letters, sequence.length()); 
    auto it = find(comb.begin(), comb.end(), sequence); 
    cout << it - comb.begin() + 1 << endl; 
 
    return 0; 
}

Answer 2

Олег Папиросик Мастер (1441) 1 год назад

на питоне:

 import itertools 
 
letters = input().strip() 
sequence = input().strip() 
 
# Generate all possible sequences of length four 
sequences = list(itertools.permutations(letters, 4)) 
 
# Sort the sequences in lexicographic order 
sequences.sort() 
 
# Find the index of the given sequence and add 1 
index = sequences.index(tuple(sequence)) + 1 
 
# Print the result 
print(index)

Garik HarlamovУченик (1) 1 год назад

49 получается, а нужно 259

Олег Папиросик Мастер (1441) Garik Harlamov,

 import itertools 
 
letters = input().strip() 
sequence = input().strip() 
 
# Generate all possible sequences of length four 
sequences = list(itertools.permutations(letters, 4)) 
 
# Sort the sequences in lexicographic order 
sequences.sort() 
 
# Find the index of the given sequence and add 1 
index = sequences.index(tuple(sequence)) + 1 
 
# Print the result 
print(index)

РеципиентГений (70042) 1 год назад

Этот код генерирует размещения без повторений, которых для алфавита из 5 символов - всего 120, и потому 259 в ответе не может получиться ни на каком языке программирования. А нужны размещения с повторениями. Чтобы придти к такому выводу, достаточно было минуту подумать перед тем, как начинать кодить.