CODEWITHSUNDEEP
algorithmsequence
johnidel127
johnidel127

Reputation: 189

Function to generate permutations of sequence with elements limited to 1 adjacent move

Let's say there is a list of length n, which contains the letters A - char(n). I want to find the permutations in which each letter can only move adjacently or remain where it is. So tor each seq, there are three "set" permutations, cycled to the left, cycled to the right(list is considered cyclic), and the original list. I'm having trouble coming up with an algorithm to deal with the possible swaps in the middle of the list. Mainly, how the pairing for letters to be swapped can skip over letters. Ex: Permutations for list where n = 3 [ABC, CAB, BCA, ACB, CBA,BAC] Also, the ABC and CAB are considered to be unique despite the elements having the same position relative to each other. Mainly looking for algorithm and not any specific language. The basic rule is that the elements may be a maximum of 1 position away from its originally position in the list.

Upvotes: 1

Views: 554

Answers (3)

rici
rici

Reputation: 241761

If I understand your problem correctly, you need to find all the permutations of a circular sequence which can be generated by selecting a non-overlapping set of adjacent pairs and swapping the two elements in each pair.

An adjacent pair can be uniquely identified by the first element in the pair; a set of adjacent pairs is non-overlapping if it does not include two consecutive elements. Without the circularity aspect, that is just fibonacci encoding: The sets of non-adjacent elements (NA) can be generated recursively as follows:

NA({a1,a2,…,an}, T) = NA({a2,a3,…,an}, T)
                      ⋃ NA({a3,a4,…,an}, T ⋃ {a1})
NA({a}, T) = { T ⋃ {a} }
NA({}, T)  = { T }

It should be clear that there are fibonacci(n + 1) sets in the final result, since the count of NA(n) is the sum of the counts of NA(n-1) and NA(n-2).

To account for the circularity, we restrict the initial case by excluding the last element if we select the first one:

CNA({a1,a2,…,an}) = NA({a2,a3,…,an}, {})
                    ⋃ NA({a3,a4,…,an-1}, {a1})

Since that's just defined in terms of NA, we can see that the count of sets for CNA is fibonacci(n) + fibonacci(n - 2).

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

I'll sketch an efficient enumeration strategy.

First let's solve the easier problem where there is no wraparound. There are two possibilities for the leftmost element. Either it stays put or moves right. If it moves right, then the element that it displaces must move left. We can enumerate the possibiltiies for the rest of the permutation recursively.

# this code is for the simpler problem, without wraparound
# the algorithm for the problem with wraparound is described in prose below

def perms_line(lst, j):
    if len(lst) - j < 2:
        print(lst)
    else:
        perms_line(lst, j + 1)
        lst[j], lst[j + 1] = lst[j + 1], lst[j]
        perms_line(lst, j + 2)
        lst[j], lst[j + 1] = lst[j + 1], lst[j]

perms_line([1, 2, 3, 4, 5], 0)

Now let's consider wraparound. If two consecutive elements move right, then every element must move right. If two consecutive elements move left, then every element must move left. Handle these exceptional permutations separately.

At the outset, consider the leftmost element. Either it stays put, is swapped with the element to its right, or is swapped with the rightmost element. For each of these three possibilities (note: two if n = 2 or just one if n = 1), use the no-wraparound enumeration strategy on the rest of the permutation. I'll pass on writing the code, since it'll take some fiddling to get right.

Upvotes: 1

Muli Yulzary
Muli Yulzary

Reputation: 2569

OK new approach:

function(String begin,String end)
  1. if size of end == 1: print begin + end.
  2. Loop end:
  3. ch = end[i]
  4. newString = remove index i from end
  5. function(begin + ch, newString)

Upvotes: 0

Related Questions