All possible permutations and related data OR other solutions

[leorob88]

I would make a program to calculate a sequence, taken from a game i played.
Basically you have a sequence of numbers, it is like a clock really, meaning they're disposed in a circle. These numbers are 1 digits only, from 1 to a max of 6, but there can be duplicates of numbers along the circle, meaning the sequence can be for example 2, 2, 3, 2, 2 (starting from top/north position and following the circumference clockwise).
The purpose of this kind of game is "selecting" ALL the numbers in the sequence but selecting them all just ONCE. You can choose where to start from. When you select a number, you can choose next only the two other numbers distancing by the number you selected. By two numbers I mean you can choose distancing forward or backwards. For examples, you select a 3, you can next select only the two numbers which have a distance of 3 from the 3. So, in the example case, the selectable values would both be 2, but in different positions. If per chance one of the two positions is unselectable, since you already selected it earlier, you cannot select it again, you can only select the others. If both are unavailable, you lose (as you indeed failed to create a sequence of selecting all numbers not selecting the same multiple times).
In the example case that I could sample like this:
2
2
3
2
2
the solution could be this (there is more than one solution in this example but this is one possible solution)
2 1st select
2 4th select
3 2nd select
2 5th select
2 3rd select
As you see, after the 3 you move backwards and so you choose the last in the list as 3rd selection. Then you move forward again restarting from the top of the list.
So, my goal would be to create a program which calculates a possible solution for this game, given a starting sequence of values. Only, the list of values can be up to 13 values. I thought also about calculating permutations but it would be 13 factorial... Once the solution is found, i need to write (messagebox, textbox, label, whatever you want) the sequence of the numbers selected and the positions in the original list (as there can be duplicate values so I need to know exactly what position that number is). How would you advice to handle this thing?

 

[Skydiver]

What's wrong with just a basic depth first tree search?

 

[leorob88]

What's wrong with just a basic depth first tree search?

Basically that I don't know what you are talking about, sorry. But I'm curious to learn!

 

[Skydiver]

See:

Depth-first search - Wikipedia

en.m.wikipedia.org

Depth-First Search (DFS)

Understand Depth-First Search (DFS) with key concepts, pseudocode, and Python examples. Explore its applications in pathfinding and puzzle-solving.

celerdata.com

 

[leorob88]

See:

Depth-first search - Wikipedia

en.m.wikipedia.org

Depth-First Search (DFS)

Understand Depth-First Search (DFS) with key concepts, pseudocode, and Python examples. Explore its applications in pathfinding and puzzle-solving.

celerdata.com

lol at first you made it sound like it should be obvious! So, I tried reading. The general concept on wikipedia i kinda get. Only I don't understand properly the code and how to apply it, even more because my case is some sort of ring/circle structure and not a tree graph, so I don't really understand how to apply this difference too. In the second one there is not even a line of code so I found it more of a conceptual explanation. The third link actually shows more comprehensible code, kinda, and the recursive code seems more useful than the iterative, only i don't know Python and

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

visited = set()
dfs_recursive(graph, 'A', visited)

Is set() supposed to be like an Array or List? Also, in the case of this code example each node in graph has assigned related data (like, A -> B, C). For the purpose of my program, I suppose these 2 should be the numbers you can select next, when you select a number? I have this doubt just because I see in this example D and F have no related nodes.

 

[leorob88]

Also, I tried to assume it's like that and i tried it in C# but it doesn't actually work. Meaning, there's an issue. What my program should do is "if you can't progress any further, restart and try a different path" but what it does instead is "if you can't progress, go backwards to unexplored other branches and write down those remaining as well". I tried to check the iterative method but actually since I don't know Python and I see there are no variables types I have a doubt.

stack : [start]

This calls the parameter..... but what is [start] supposed to be? In theory, it is a string but maybe it is handling it as a string array...? I don't understand... So, briefly, to at least understand what this code actually does, it would be nice to have it translated to C#...

 

[Skydiver]

You have a fun little problem, and I'm trying not to just spoonfeed you the answer because you seem to enjoy learning, and I don't want to deprive you of the joy of that "A-ha!" moment.

Perhaps this might help a bit more since it a little more visual. Sorry, it's Python again, but the concepts should be a lot clearer.

Morse Code using a Binary Tree - 101 Computing

The Morse Code was designed to quickly transfer messages using a series of "dots (.)" and "dashes (-)". Morse code was named after Samuel Morse, one of the inventors of the telegraph. The International Morse Code includes the 26 letters of the alphabet (there is no distinction between lowercase...

www.101computing.net

As for the circular array that you have: the modulus operator % is your friend. Let's you you have an array of length 5, and you are currentyl at index 4:

2 2 3 2 2 -- value
        ^
0 1 2 3 4 -- index

So given the value of 2 in your array, you are can go back 2 or advance by 2. To handle the advance case, if you add do (4 + 2) % 5, you get the result of 1:

2 2 3 2 2 -- value
  ^
0 1 2 3 4 -- index

(Alas, the C# modulus operator trick won't work on the go back case. For that you'll need to do bounds check.)