Hi all,
For a research project I am conducting, I have come across an algorithms problem. I would like a solution which runs in at most 1 hour or so. Can someone give me an idea? Thank you!
Find all permutations a such that a has 28 elements and:
a has 8 cycles of length 3 and 4 fixed points b is ({1,2,3...,7}, {8,9,10...,14}, {15,16,17...,21}, {22,23,24,...,28}) cycle structure a * b has 14 cycles of length 2.
Are you sure there is at least one such permutation? If so, could you please give an example?
My program terminates in under a second but does not find a solution. Nor does it find any solution for a scaled-down version of length 14, even with no nontrivial optimizations.
Imperative programming is not a good fit for such problems in general. I'd be interested to see a more declarative solution with some right tool, like Prolog perhaps.
No, I do not know of a single answer to the problem, and a very distinct possibility was no solutions. Thank you!
EDIT: I have been notified that a solution does, in fact, exist to this problem.
Hmm, and I found a bug in my program. Now it takes about 20 seconds and gives 84 permutations. The source and the list are here.
I still suspect it's wrong, since the output lacks basic symmetry: for example, the first number is from {1, 12, 19, 22-28}, but I'd expect 12 and 19 not to have any special properties compared to say 13 and 20.
If however the permutations in the list do in fact meet your criteria, then I at least got the problem statement right.
The number of permutations which work are equal to
1290482565120000, so you have still not found all the solutions.
The permutations you listed are correct. Could you write a program for a = [1^2, 3^4] b = [1^2, 2^6] a*b = [7^2]?
1290482565120000 is 2·(7!)4, so it makes sense here. But you won't be able to do anything with this much permutations anyway. If we consider, say, one million permutations per second, we will still need more than a billion seconds to cover them all, which is clearly more than an hour.
As for the other problem you propose, perhaps some more general solution can be thought of, to take care of all possible instances of the underlying problem.
There are fewer essentially different solutions, since if you have any permutation a solving the original problem, and g is any permutation which commutes with b, then g a g^{-1} also solves the original problem. So it suffices to give one representative for each such equivalence class of solutions. For instance, all 84 of your solutions are equivalent to one another. The number of permutations that commute with b is 4!*7^4 = 57624, so this cuts down the size of the answer by a lot.
Here is a permutation which satisfies the requirements of the problem but isn't on your list:
1 7 15 11 24 19 16 26 9 8 25 3 21 22 12 2 6 18 17 5 23 27 13 20 4 10 14 28