Help with a special case of permutations algorithm (not the usual)

Question

Hi, Friends.

I have always been interested in algorithms, sort, crypto, binary trees, data compression, memory operations, etc.

I read Mark Nelson's article about permutations in C++ with the STL function next_perm(), very interesting and useful, after that I wrote one class method to get the next permutation in Delphi, since that is the tool I presently use most. This function works on lexographic order, I got the algo idea from a answer in another topic here on stackoverflow, but now I have a big problem. I'm working with permutations with repeated elements in a vector and there are lot of permutations that I don't need. For example, I have this first permutation for 7 elements in lexographic order:

6667778 (6 = 3 times consecutively, 7 = 3 times consecutively)

For my work I consider valid perm only those with at most 2 elements repeated consecutively, like this:

6676778 (6 = 2 times consecutively, 7 = 2 times consecutively)

In short, I need a function that returns only permutations that have at most N consecutive repetitions, according to the parameter received.

Does anyone know if there is some algorithm that already does this?

Sorry for any mistakes in the text, I still don't speak English very well.

Thank you so much, Carlos

Answer 1

So, in the homework-assistance kind of way, I can think of two approaches.

Work out all permutations that contain 3 or more consecutive repetitions (which you can do by treating the three-in-a-row as just one psuedo-digit and feeding it to a normal permutation generation algorithm). Make a lookup table of all of these. Now generate all permutations of your original string, and look them up in lookup table before adding them to the result.

Use a recursive permutation generating algorthm (select each possibility for the first digit in turn, recurse to generate permutations of the remaining digits), but in each recursion pass along the last two digits generated so far. Then in the recursively called function, if the two values passed in are the same, don't allow the first digit to be the same as those.

Answer 2

Paul, thanks in advance.

But at the point where I am, it would be need a function that would be able to return the next permutation with only N at most repeated elements consecutively.

I believe it is possible to return the next permutation without the need for recursive functions or pass through previous permutations (like next_perm() for lexographic order). Otherwise, the processing will be impracticable due a too long time even for very small input datasets.

I'll burn my mind on that issue :-).

It's something like that:

tail_beginning := n;
for n := len - 1 downto tail_beginning do
begin
    if anyVector[n] > anyVector[tail_beginning - 1] then
    begin

        //At this point, only allow the swap below if the number of consecutive 
        //repeated elements is not greater than X

        aux := anyVector[n];
        anyVector[n] := anyVector[tail_beginning - 1];
        anyVector[tail_beginning - 1] := aux;
        Break;
    end;
end;

Suggestions are welcome.

Answer 3

Why not just make a wrapper around the normal permutation function that skips values that have N consecutive repetitions? something like:

(pseudocode)

funciton custom_perm(int max_rep)
  do
    p := next_perm()
  while count_max_rerps(p) < max_rep
  return p

Answer 4

Krusty, I'm already doing that at the end of function, but not solves the problem, because is need to generate all permutations and check them each one.

consecutive := 1;
IsValid := True;
for n := 0 to len - 2 do
begin
    if anyVector[n] = anyVector[n + 1] then
        consecutive := consecutive + 1
    else
        consecutive := 1;
    if consecutive > MaxConsecutiveRepeats then
    begin
        IsValid := False;
        Break;
    end;
end;

Since I do get started with the first in lexographic order, ends up being necessary by this way generate a lot of unnecessary perms.

Answer 5

This is easy to make, but rather hard to make efficient.

If you need to build a single piece of code that only considers valid outputs, and thus doesn't bother walking over the entire combination space, then you're going to have some thinking to do.

On the other hand, if you can live with the code internally producing all combinations, valid or not, then it should be simple.

Make a new enumerator, one which you can call that next_perm method on, and have this internally use the other enumerator, the one that produces every combination.

Then simply make the outer enumerator run in a while loop asking the inner one for more permutations until you find one that is valid, then produce that.

Pseudo-code for this:

generator1:
    when called, yield the next combination

generator2:
    internally keep a generator1 object
    when called, keep asking generator1 for a new combination
        check the combination
        if valid, then yield it

Answer 6

My approach is a recursive generator that doesn't follow branches that contain illegal sequences.

Here's the python 3 code:

def perm_maxlen(elements, prefix = "", maxlen = 2):
    if not elements: 
        yield prefix + elements
        return

    used = set()

    for i in range(len(elements)):
        element = elements[i]
        if element in used:
            #already searched this path
            continue

        used.add(element)

        suffix = prefix[-maxlen:] + element
        if len(suffix) > maxlen and len(set(suffix)) == 1:
            #would exceed maximum run length
            continue

        sub_elements = elements[:i] + elements[i+1:]
        for perm in perm_maxlen(sub_elements, prefix + element, maxlen):
            yield perm


for perm in perm_maxlen("6667778"):
    print(perm)

The implentation is written for readability, not speed, but the algorithm should be much faster than naively filtering all permutations.

print(len(perm_maxlen("a"*100 + "b"*100, "", 1)))

For example, it runs this in milliseconds, where the naive filtering solution would take millenia or something.