Блог

Я хотел бы вывести все похожие числа числа, где:

1. Каждая пара смежных цифр также встречается в исходном числе.
2. Новые числа содержат то же количество цифр, что и исходные
3. Порядок, в котором генерируются числа, не имеет значения

Например, предположим, что мне дано число 12314, тогда у меня есть пары 12,23,31,14

Я должен генерировать [12314,31231,12312,23123] .

Если мне даны числа типа 52 или 11111, то я должен получить только 52/11111 соответственно.

Я уже написал код, который генерирует пары [12,23,31,14] , и генерирует все возможные перестановки этого списка пар. Однако перестановки приводят к числам, которые длиннее исходных, и многие из этих перестановок недопустимы. Например, когда 1214 появляется в перестановке, перестановка недействительна, поскольку «21» отсутствует в исходном числе.

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

Вы можете использовать рекурсию для генерации требуемых чисел.

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

 // pairs[i][j] is true if j is immediately after i in the original number
bool pairs[10][10];

// curr_num is a valid number according to the constraint given
// curr_len is the number of digits in curr_num
// length is the number of digits in the number given
void generate(int curr_num, int curr_len, int length){
    if(cur_len == length){
         display curr_num;
     } else {
        // extract last digit amp; check what digits can follow that
        int last = curr_num % 10;
        for(int i = 0 ; i <= 9 ; i  )
            if(pairs[last][i])
                generate(curr_num * 10   i , curr_len   1, length); 
    }
}

for(digit in original_number)
    generate(digit, 1, length);
  

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