Next lexical "permutation" algorithm

Question

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 kth 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.

The problem smells NP-Complete. When the only binary operation is addition this is the same as the subset sum problem. Perhaps one of the branch and bound approaches for that is applicable. In the worst case, though, we probably cannot determine a polynomial time solution. — AndyG, Nov 11 '16 at 19:52
Possible duplicate of [Algorithm to find next greater permutation of a given string](http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string) — Pikalek, Nov 11 '16 at 20:00
How is `{‘o’,’o’,’o’,’v’,’v’,’v’,’v’}` a valid infix expression? Do you mean prefix expression? — AndyG, Nov 11 '16 at 20:02
[`std::next_permutation`](http://en.cppreference.com/w/cpp/algorithm/next_permutation) can be used to generate lexicographical permutations. I do not know of any algorithm for generating the Nth permutation (besides calling `std::next_permutation` N times). — Cornstalks, Nov 11 '16 at 20:10
Yes. In fact, I'm using `std::next_permutation` in my current implementation. However, I want to find the next valid permutation. — Tigin, Nov 11 '16 at 20:12
It's possible -- even easy -- to iterate through all such expressions efficiently. But you'll definitely want to use a better data structure than strings. — Daniel Wagner, Nov 11 '16 at 20:13
I would suggest generating an AST for expression directly. It could go like this: given a set of numbers, if there's only one number, return it. Otherwise, iterate over all operations and all partitions of the the set into two non-empty sets. Recursively generate all values for the two subsets. Combine them using the operation. — kraskevich, Nov 11 '16 at 20:17

David Eisenstat · Accepted Answer · 2016-11-11T20:31:46.487

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.

Next lexical "permutation" algorithm

What I have so far

1 Answers1