C ++: генерировать комбинации в новой базе - PullRequest
Новая
       18

C ++: генерировать комбинации в новой базе

1 голос
/ 14 марта 2019

Я пытаюсь по существу рассчитывать на новую базу, заданную заданным алфавитом.Поэтому для следующих параметров: 

#define ALPHABET "abc"
#define ALPHABET_LEN 3

Я бы получил следующий результат: 

0 | a
1 | b
2 | c
3 | aa
4 | ab
...
9 | ca
10| cb

Я попытался сделать это с помощью следующего кода: 

#include <iostream>
#include <string>

#define ALPHABET "abc"
#define ALPHABET_LEN 3

int main()
{
    for (int i = 0; i <= 10; i++) {
        int l = 0;
        int n_ = i;
        int n = i;
        char secret[4];

        while (n > 0) {
            secret[l] = ALPHABET[n%ALPHABET_LEN];
            n /= ALPHABET_LEN;
            l++;
        }
        std::cout << i << " | " << secret << std::endl;
    }
}

К сожалению, это печатает следующее: 

0 | 
1 | b
2 | c
3 | ab
4 | bb
5 | cb
6 | ac
7 | bc
8 | cc
9 | aab
10 | bab

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

Ответы [ 2 ]

1 голос
/ 14 марта 2019

Это сложная проблема алгоритма. Описание проблемы вводит в заблуждение. Базовое преобразование предполагает, что будет нулевое значение, которое будет примерно таким:

a, b, c, a0, aa, ab, ac, b0, b1, b2, c0 и т. Д.

Однако в этой задаче «а» представляет «ноль», но «а» также является первой цифрой.

Рассматривая это как базовое преобразование, можно создать кроличью нору сложности.

Скорее, нужно выяснить алгоритм вычисления каждой последующей цифры и игнорировать идею преобразования базы.

Первый подход состоит в том, чтобы придумать формулу для каждой цифры, которая выглядит следующим образом: 

int LEN = ALPHABET_LEN;  // Use a shorter variable name

std::string = ALPHABET[i % LEN];  // first digit
if(i > LEN - 1) {
  secret = ALPHABET[(i/LEN -1)%LEN] + secret;
}

if(i > LEN * (LEN+1) - 1) {
  secret = ALPHABET[(i/(LEN *(LEN+1)) - 1)%LEN] + secret;
}

if(i > LEN * (LEN+1) *(LEN+1) - 1) {
  secret = ALPHABET[(i/(LEN *(LEN+1) * (LEN+1) ) - 1)%LEN] + secret;
}

Когда вы разрабатываете формулу для каждой последующей цифры, вы понимаете, что основание действительно LEN + 1, а не LEN.

Этот подход работает, но он всегда требует дополнительного оператора if для каждой последующей цифры. Конечно, для i = 1 .. 10 это работает нормально. Но что, если я = 10 000 000 Это потребовало бы бесконечной последовательной серии операторов if.

Однако, после обнаружения шаблона, теперь немного проще создать оператор while (), который устраняет необходимость в бесконечной серии операторов if. 

#include <iostream>
#include <string>

//works as #define, but I like string so I can easily test with 
// longer strings such as "abcd"
std::string ALPHABET {"abc"};  

int main()
{

  const int LEN = ALPHABET.size();  // Shorten the var name

  for (int i = 0; i <= 100; i++) { // use i <= 100 to verify the algorithm

    int number = i;  // save the number that we are working on for this row
    std::string secret = "";

    secret += ALPHABET[i % LEN];
    while(number / LEN > 0){
      number = number/LEN - 1;  // the base is really 4 rather than 3
      secret = ALPHABET[number%LEN] + secret;
    }
    std::cout << i << " | " << secret << std::endl;
  }
}

Вывод будет: 

0 | a
1 | b
2 | c
3 | aa
4 | ab
5 | ac
6 | ba
7 | bb
8 | bc
9 | ca
10 | cb
11 | cc
12 | aaa
13 | aab
14 | aac
15 | aba
16 | abb
17 | abc
18 | aca
19 | acb
20 | acc
21 | baa
22 | bab
23 | bac
24 | bba
25 | bbb
26 | bbc
27 | bca
28 | bcb
29 | bcc
30 | caa
31 | cab
32 | cac
33 | cba
34 | cbb
35 | cbc
36 | cca
37 | ccb
38 | ccc
39 | aaaa
40 | aaab
41 | aaac
42 | aaba
43 | aabb
44 | aabc
45 | aaca
46 | aacb
47 | aacc
48 | abaa
49 | abab
50 | abac
51 | abba
52 | abbb
53 | abbc
54 | abca
55 | abcb
56 | abcc
57 | acaa
58 | acab
59 | acac
60 | acba
61 | acbb
62 | acbc
63 | acca
64 | accb
65 | accc
66 | baaa
67 | baab
68 | baac
69 | baba
70 | babb
71 | babc
72 | baca
73 | bacb
74 | bacc
75 | bbaa
76 | bbab
77 | bbac
78 | bbba
79 | bbbb
80 | bbbc
81 | bbca
82 | bbcb
83 | bbcc
84 | bcaa
85 | bcab
86 | bcac
87 | bcba
88 | bcbb
89 | bcbc
90 | bcca
91 | bccb
92 | bccc
93 | caaa
94 | caab
95 | caac
96 | caba
97 | cabb
98 | cabc
99 | caca
100 | cacb

Process finished with exit code 0
0 голосов
/ 14 марта 2019 
int i = 0;
int n = i;
while (n > 0) {

Очевидно, что в первой итерации внутренний цикл не будет запускать ни одной итерации, и, таким образом, secret не будет содержать a, как следует.

P.S. Не удается завершить нулем secret, поэтому поведение программы не определено при вставке его в выходной поток.

...