I'll explain my problem with an analogy to Sudoku-grids.
Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However the new grid is essentially equivalent, if that makes sense. One might say, under the operations "swap rows", "exchange labels" etc., both grids are in the same orbit. (https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions)
I want to iterate over all grids, but in a way that the algorithm ignores other solutions in the same orbit. However, this question is not about Sudoku grids! My grids have a different structure, which is a bit simpler:
I want to fill a 4x6 table with the integers 1 to 8 (each three times) such that each row contains each integer at most once. There are a few other more complex conditions, but I think it's easier to check them later after a solution has been generated.
Just like in the Sudoku analogy, there are a few operations that generate other essentially equivalent solutions:
1) Rearranging rows: if one row is
1 3 5 6 2 8
the solution with that row replaced by
1 2 3 5 6 8
is of course also valid and consindered essentially equivalent.
2) Swapping rows.
3) Exchanging labels.
E.g. these solutions are essentially equivalent
1 3 5 6 2 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7
First row rearranged:
1 2 3 5 6 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7
First two rows swapped:
4 1 5 7 8 2
1 3 5 6 2 8
4 7 6 1 2 3
3 4 5 6 8 7
All 1's and 2's exchanged
2 3 5 6 1 8
4 2 5 7 8 1
4 7 6 2 1 3
3 4 5 6 8 7
My question is what an efficient (both runtime and memory) algorithm to generate these solutions might be.
The naive approach would be to store all previous solutions and check whether an equivalent solution has already been found. However, this is expensive in both runtime and memory!
I managed to improve this by calculating a hash of each solution in such a way that equivalent solutions generate the same hash. Then we can store the solutions in a map, so that we need to check fewer solutions and thus reduce the runtime. However, the memory cost is still huge.
If the hash has the property that different solutions yield different hashes, then I would only need to store the hashes and reduce the required memory by a large factor.
Can you think of a more elegant algorithm that does not store hashes nor previous solutions?
EDIT:
I simplified my problem too much without realising that I reduced the number of orbits to 1. (Thanks @Klaus Draeger). In fact the numbers 4,6,8 and 3 were made up as an example. I thought I could adapt the algorithm to the more general case later. Actually, my problem is a bit more complex: The number of rows is variable and rows need not have the same length, so rule 2) only applies to rows of equal length. Also the frequency of the numbers is not necessarily constant (e.g numbers 1,2,3,4 might appear four times and 5,6,7,8 three times or whatever), so rule 3) only applies to labels with the same frequency.
EDIT2:
And this is the more complex condition, that I thought doesn't matter for now. Maybe I'm wrong again...
If, in one row, y appears directly to the right of x (or y is in the first column and x in the last), then in a (unique) different row there must be an x to the right of y (above example does not satisfy this). This means that rule 1) only applies to rotations of rows and not any permutation.
I think this can be dealt with at a later point.
