[Python] I want to generate a permutation to check it satisfies an equation before I generate...

I'm writing code to find a convex n-gon with side lengths 1^k,2^k,...,n^k with equal interior angles. If we formulate this as an algebra problem on the complex plane, this is satisfied using the following equations:

1. w^n-1=0
2. a_1+a_2w+...+a_nw^{n-1}=0

where a_1,a_2,...,a_n is some permutation of 1^k,2^k,...,n^k with no repeats.

I know that k < number of distinct prime factors of n

My code fixes an n, k, and w (at the moment n=12 and k=1 as it takes too long to generate any shape n>12 and w=e^{(2*i*pi)/n})

I'm currently using itertools to generate all permutations of the side lengths and then iterating through them to find a permutation that satisfies my equations and then it breaks.

I've already accounted for rotations by fixing a start length, but it's still really slow. I was wondering if I could write some code such that I can check if a permutation satisfies my equations before generating the next permutation to check. This would significantly reduce my runtime as I only need one permutation that works.

Continue reading...