Generuj liczby gdzie każda para sąsiednich cyfr występuje również w pierwotnej liczbie - algorytm, permutacja

Chciałbym wypisać wszystkie podobne numery liczby, gdzie:

1. Każda para sąsiednich cyfr występuje również w pierwotnym numerze.
2. Nowe liczby mają taką samą liczbę cyfr jak oryginał
3. Kolejność, w jakiej liczby są generowane, nie ma znaczenia

Załóżmy na przykład, że mam podaną liczbę 12314, a następnie mam pary 12 23, 3, 31, 14

Powinienem generować [12314,31231,12312,23123].

Jeśli otrzymam liczby takie jak 52 lub 11111, to powinienem otrzymać tylko 52/11111.

Napisałem już kod generujący pary [12,23,31,14]i wygenerować wszystkie możliwe kombinacje tegolista par. Jednak permutacje generują liczby dłuższe niż oryginał, a wiele z tych permutacji jest nieważnych. Na przykład, kiedy 1214 pojawia się w permutacji, permutacja nie jest ważna, ponieważ "21" nie ma oryginalnego numeru.

Chciałbym wiedzieć, jak postępować. Wygląda to bardzo nieefektywnie, aby odfiltrować nieprawidłowe z wszystkich permutacji.

Odpowiedzi:

Możesz użyć rekurencji do wygenerowania wymaganych liczb.

Chodzi o to, aby zachować tylko ważne numery na dowolnym etapie i wyświetlać, gdy pierwotna długość i długość twojej liczby są równe.

// 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 & 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);

Możesz zoptymalizować kod, tworząc pary lista przyległości niż macierz sąsiedztwa.