Strings of Numbers

We need to find a ‘S’ string that contains all possible permutations of length ‘N’ and allowed characters ‘0’ to ‘K’. So there can be total ‘(K + 1) ^ N’ possible permutations, For example if ‘N’ is 2 and ‘K’ is 1 then total possible permutations are { 00, 01, 10, 11} i.e 2 ^ 2 = 4 total possible. We can simply concatenate each one to find such ‘S’ i.e ‘S’  = “00011011”, but in order to minimise the length of ‘S we need to make sure that every permutation occurs exactly once in the ‘S’. Such strings are made from De Bruijn sequence. We can visualise the given Problem as a directed graph structure where each node represents distinct possible permutations of length ‘N’ and a edge from ‘node1’ to ‘node2’ represents that we can add a digit in range [0, k] to the suffix of length ‘N - 1’ of ‘node1’ to make ‘node2’.

For example for ‘N’ = 2 and ‘K’ = 2, the graph structure will look like below.

Now we just need to find a Hamiltonian Path in the above graph and add the character of edges in the path to the starting string. For example, let's start with ‘00’ and initialize our answer with ‘00’.

• We move to ‘01’ and add ‘1’ to answer.
• Now we will move to ‘11’ because if we move to ‘10’, we got stuck, so add ‘1’ to answer.
• Now from ‘11’ we move to ‘10’, thus completing our path, and hence the answer becomes ‘00110’.

We can run a dfs with a backtrack to find such a path.

Algorithm:

• Let the given integers be ‘N’ and ‘K’
• Declare a function dfs to visit all nodes in the graph once.
• Declare a hashmap of string say ‘visited’ to keep track of the visited strings (nodes) in the graph.
• Declare a string ‘answer’ and initialize it with ‘000… N times’.
• Insert ‘answer’ into ‘visited’.
• Call the dfs function to find a hamiltonian path.
• Return ‘answer’.

Description of ‘dfs’ function

This is a boolean function that returns true if we find a valid path by traversing an edge, else return false.

The function will take four-parameter:

‘N’: The given length of numbers

‘K’: allowed range of digits

‘answer’: global answer string

‘visited’:  A hashmap to keep track of visited nodes.

bool dfs ( N, K, answer, visited ):

• If we have visited all the nodes i.e. the size of ‘visited’ is (‘K’ + 1) ^ ‘N’
  • return true.
• Run a loop from ‘i’ = 0 to ‘K’
  • Declare a string say ‘currNode’ and set it to substring ‘answer(1, N-1)’.
  • Add string of ‘i’ to ‘currNode’.
  • If ‘currNode’ is not visited.
    • Insert ‘currNode’ into ‘visited’.
    • Check if adding ‘i’ to 'answer' is a valid path or not i.e If dfs( ‘answer’ + ‘str(i)’) == true then
      • Return true.
    • Else:
      • Remove ‘currNode’ from ‘visited’, as we cannot add ‘i’ to ‘answer’ now.
• Return false.

As we see in the previous approach, the required string can be obtained from the De Bruijn sequence. The idea is to start with ‘N’ 0’s as an initial answer and greedily add digits until we get all the possible permutations. But in order to prevent stuck situations as we see in the example of the previous approach, we need to add digits in a post-order way. i.e starting from ‘K’ to ‘0’. For example ‘N’ = 2 and ‘K’ is 1, and if the previous permutation is ‘01’ then we will first add ‘1’ to get ‘11’ and then add ‘0’.

Algorithm:

• Let the given integers be ‘N’ and ‘K’
• Declare a hashmap of string say ‘visited’ to keep track of the visited strings.
• Declare a string ‘answer’ and initialize it with ‘000… N times’.
• Insert ‘answer’ into ‘visited’.
• Run a loop until the size of ‘visited’ is less than (‘K’ + 1) ^ ‘N’, i.e we visited all permutations.
  • Declare a string say ‘previous’ to store the last ‘N - 1’ characters of ‘answer’.
  • Run a loop from ‘i’ = K to ‘0’.
    • If ‘previous’ + string form of ‘i’ is not visited
      • Add ‘previous’ + str(‘i’) into ‘visited’.
      • Add str(‘i’) in ‘answer’.
      • Break the current loop.
• Return ‘answer’.