A set of strings equivalent under rotation. Example: (100, 010, 001) is the set of necklaces with one 1 and two 0s, only one of these needs to be known since they are all equivalent under rotation.
Questions tagged [necklaces]
3 questions
13
votes
5 answers
Is there an algorithm to generate all unique circular permutations of a multiset?
I encountered this problem when doing some enthusiastic programming. The problem can be expressed as follows:
For a multiset A, let P(A) denote the
set of all possible permutations of A.
P(A) is naturally divided into
disjoint subsets that…
Cong Ma
- 10,692
- 3
- 31
- 47
11
votes
6 answers
Unique permutations with no mirrored or circular repetitions
Some background: I'm writing a more or less brute force search algorithm for solving a problem that I have. In order to do this, I need to generate and evaluate all possibilities to find out which is best. Since the evaluation actually takes some…
Jordi
- 5,846
- 10
- 40
- 41
7
votes
4 answers
Good simple algorithm for generating necklaces in Scheme?
A k-ary necklace of length n is an ordered list of length n whose items are drawn from an alphabet of length k, which is the lexicographically first list in a sort of all lists sharing an ordering under rotation.
Example:
(1 2 3) and (1 3 2) are the…
Carl Lumma