1 vote

Efficient algorithms to generate partial permutations?

You can use immutable, singly linked lists to generate partial permutations in $O(n \operatorname{choose} k)$ operations and memory, which is likely optimal. Here's an example in the Scala programming ...
DirkT's user avatar
  • 991
1 vote

Heap's Algorithm for k-permutations?

Yes, and the idea behind the modification is fairly straightforward. Using a C-like notation, this is Heap's algorithm: ...
Pseudonym's user avatar
  • 22.1k
1 vote

Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition

No, these 3 conditions are not sufficient. For example, $n=4$, $A=[6,5,2,1]$, $B=[1,3,4,6]$, $k=7$. The sum of all elements in $A$ and $B$ is $14+14=28=4\cdot7$. The sum of the max in $A$ and the min ...
John L.'s user avatar
  • 39k
1 vote

Are permutations of context-free languages context-free?

No, in general not. For example the MIX language, consisting of equal numbers of $\{a,b,c\}$ in any order is not context-free but is the permutation of the regular language $(abc)^*$.
Alexander Clark's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible