# Tag Info

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 ...
• 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: ...
• 22.1k
1 vote
Accepted

### 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 ...
• 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)^*$.

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