Tigin Tigin - 27 days ago 11
C++ Question

Next lexical "permutation" algorithm

I wrote a program that solves a generalized version of 24(link for those curious). That is, given a set of

n
numbers, is there a way to perform binary operations on them such that they compute to a target number.

To do this, I viewed possible expressions as a char array consisting of either
'v'
or
'o'
, where
'v'
is a placeholder for a value and
'o'
is a placeholder for an operation. Note that if there are
n
values, there must be
n-1
operations.

How the program currently works is it checks every permutation of
{'o','o',...,'v',v'...}
in lexicographical order and sees if the prefix expression is valid. For example, when
n = 4
, the following expressions are considered valid:

{‘o’,’o’,’o’,’v’,’v’,’v’,’v’}


{‘o’, ‘v’, ‘o’, ‘v’, ‘o’, ‘v’, ‘v’}


The following expressions are not valid:

{‘v’,’o’,’v’,’o’,’o’,’v’,’v’}


{‘o’,’o’,’v’,’v’,’v’,’o’,’v’}


My question is does there exist an efficient algorithm to get the next permutation that is valid in some sort of ordering? The goal is to eliminate having to check if an expression is valid for every permutation.

Moreover, if such an algorithm exists, does there exist an
O(1)
time to compute the
k
th valid permutation?

What I have so far



I hypothesize that an prefix expression
A
of length
2n-1
is considered valid if and only if

number of operations < number of values
for each
A[i:2n-1)


where
0<=i<2n-1
(the subarray starting at
i
and ending (non-inclusive) at
2n-1
)

Moreover, that implies there are exactly
(1/n)C(2n-2,n-1)
valid permutations where
C(n,k)
is
n choose k
.

Answer

Here's how to generate the ov-patterns. The details behind the code below are in Knuth Volume 4A (or at least alluded to; I might have worked one of the exercises). You can use the existing permutation machinery to permute the values every which way before changing patterns.

The code

#include <cstdio>

namespace {
void FirstTree(int f[], int n) {
  for (int i = n; i >= 0; i--) f[i] = 2 * i + 1;
}

bool NextTree(int f[], int n) {
  int i = 0;
  while (f[i] + 1 == f[i + 1]) i++;
  f[i]++;
  FirstTree(f, i - 1);
  return i + 1 < n;
}

void PrintTree(int f[], int n) {
  int i = 0;
  for (int j = 0; j < 2 * n; j++) {
    if (j == f[i]) {
      std::putchar('v');
      i++;
    } else {
      std::putchar('o');
    }
  }
  std::putchar('v');
  std::putchar('\n');
}
}

int main() {
  constexpr int kN = 4;
  int f[1 + kN];
  FirstTree(f, kN);
  do {
    PrintTree(f, kN);
  } while (NextTree(f, kN));
}

generates the output

ovovovovv
oovvovovv
ovoovvovv
oovovvovv
ooovvvovv
ovovoovvv
oovvoovvv
ovoovovvv
oovovovvv
ooovvovvv
ovooovvvv
oovoovvvv
ooovovvvv
oooovvvvv

There's a way to get the kth tree, but in time O(n) rather than O(1). The magic words are unranking binary trees.