Generate All Permutations of a List Without Adjacent Equal Elements

Generate all permutations of a list without adjacent equal elements

This is along the lines of Thijser's currently incomplete pseudocode. The idea is to take the most frequent of the remaining item types unless it was just taken. (See also Coady's implementation of this algorithm.)

import collections
import heapq

class Sentinel:
    pass

def david_eisenstat(lst):
    counts = collections.Counter(lst)
    heap = [(-count, key) for key, count in counts.items()]
    heapq.heapify(heap)
    output = []
    last = Sentinel()
    while heap:
        minuscount1, key1 = heapq.heappop(heap)
        if key1 != last or not heap:
            last = key1
            minuscount1 += 1
        else:
            minuscount2, key2 = heapq.heappop(heap)
            last = key2
            minuscount2 += 1
            if minuscount2 != 0:
                heapq.heappush(heap, (minuscount2, key2))
        output.append(last)
        if minuscount1 != 0:
            heapq.heappush(heap, (minuscount1, key1))
    return output

Proof of correctness

For two item types, with counts k1 and k2, the optimal solution has k2 - k1 - 1 defects if k1 < k2, 0 defects if k1 = k2, and k1 - k2 - 1 defects if k1 > k2. The = case is obvious. The others are symmetric; each instance of the minority element prevents at most two defects out of a total of k1 + k2 - 1 possible.

This greedy algorithm returns optimal solutions, by the following logic. We call a prefix (partial solution) safe if it extends to an optimal solution. Clearly the empty prefix is safe, and if a safe prefix is a whole solution then that solution is optimal. It suffices to show inductively that each greedy step maintains safety.

The only way that a greedy step introduces a defect is if only one item type remains, in which case there is only one way to continue, and that way is safe. Otherwise, let P be the (safe) prefix just before the step under consideration, let P' be the prefix just after, and let S be an optimal solution extending P. If S extends P' also, then we're done. Otherwise, let P' = Px and S = PQ and Q = yQ', where x and y are items and Q and Q' are sequences.

Suppose first that P does not end with y. By the algorithm's choice, x is at least as frequent in Q as y. Consider the maximal substrings of Q containing only x and y. If the first substring has at least as many x's as y's, then it can be rewritten without introducing additional defects to begin with x. If the first substring has more y's than x's, then some other substring has more x's than y's, and we can rewrite these substrings without additional defects so that x goes first. In both cases, we find an optimal solution T that extends P', as needed.

Suppose now that P does end with y. Modify Q by moving the first occurrence of x to the front. In doing so, we introduce at most one defect (where x used to be) and eliminate one defect (the yy).

Generating all solutions

This is tobias_k's answer plus efficient tests to detect when the choice currently under consideration is globally constrained in some way. The asymptotic running time is optimal, since the overhead of generation is on the order of the length of the output. The worst-case delay unfortunately is quadratic; it could be reduced to linear (optimal) with better data structures.

from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange

def get_mode(count):
    return max(count.items(), key=itemgetter(1))[0]

def enum2(prefix, x, count, total, mode):
    prefix.append(x)
    count_x = count[x]
    if count_x == 1:
        del count[x]
    else:
        count[x] = count_x - 1
    yield from enum1(prefix, count, total - 1, mode)
    count[x] = count_x
    del prefix[-1]

def enum1(prefix, count, total, mode):
    if total == 0:
        yield tuple(prefix)
        return
    if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:
        yield from enum2(prefix, mode, count, total, mode)
    else:
        defect_okay = not prefix or count[prefix[-1]] * 2 > total
        mode = get_mode(count)
        for x in list(count.keys()):
            if defect_okay or [x] != prefix[-1:]:
                yield from enum2(prefix, x, count, total, mode)

def enum(seq):
    count = Counter(seq)
    if count:
        yield from enum1([], count, sum(count.values()), get_mode(count))
    else:
        yield ()

def defects(lst):
    return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))

def test(lst):
    perms = set(permutations(lst))
    opt = min(map(defects, perms))
    slow = {perm for perm in perms if defects(perm) == opt}
    fast = set(enum(lst))
    print(lst, fast, slow)
    assert slow == fast

for r in range(10000):
    test([randrange(3) for i in range(randrange(6))])

Is there a way to get all permutations with the condition of unique adjacent elements?

Can you please check if that solution matches your expectations? If so, I can provide some explanation.

from itertools import combinations

def three_letters_sub_set(letters):
    return combinations(letters, 3)

def adjacent_letters_sub_set(letters):
    for position in range(len(letters) - 1):
        adjacent_letters = (letters[position], letters[position + 1])
        yield position, adjacent_letters

def fails_rule2(letters):
    return any(
        three_letters in existing_three_letter_tuples
        for three_letters in three_letters_sub_set(letters)
    )

def fails_rule3(letters):
    for position, adjacent_letters in adjacent_letters_sub_set(letters):
        if adjacent_letters in existing_adjacent_letters[position]:
            return True
    return False

n_letters = 5
existing_three_letter_tuples = set()
existing_adjacent_letters = {position: set() for position in range(n_letters - 1)}

for comb in combinations(Letters, n_letters):
    if fails_rule2(comb):
        continue
    if fails_rule3(comb):
        continue

    existing_three_letter_tuples.update(three_letters_sub_set(comb))
    for position, adjacent_letters in adjacent_letters_sub_set(comb):
        existing_adjacent_letters[position].add(adjacent_letters)

    print(comb)

How to compute all unique permutations and keep the same positive adjacent elements always adjacent?

We can first compress the given array so that there is just one entry for every positive number, while keeping a count of how many times each number occurred (the zeroes should be left as is).
Generate the permutations of the compressed array.
Decompress each of the permutation and retain only the unique ones.

To Compress

def compress(arr):
    counts = {}
    compressed = []
    curr_ele = arr[0]
    count_ele = 0
    for ele in arr:
        if ele != curr_ele or ele == 0:
            counts[curr_ele] = count_ele
            compressed.append(curr_ele)
            count_ele = 1
            curr_ele = ele
        else:
            count_ele += 1
    counts[curr_ele] = count_ele
    compressed.append(curr_ele)
    return compressed, counts

To Uncompress

def uncompress(arr, counts):
    res = []
    for ele in arr:
        if ele == 0:
            res.append(0)
            continue
        num_reps = counts[ele]
        for _ in range(num_reps):
            res.append(ele)
    return res

Putting it together: Compress, Permute, Uncompress and Retain Unique

import itertools
ip = [2, 3, 3, 0, 0]
ip_compressed, counts = compress(ip)
set([tuple(uncompress(perm, counts)) for perm in itertools.permutations(ip_compressed)])

Result:

{(0, 0, 2, 3, 3),
 (0, 0, 3, 3, 2),
 (0, 2, 0, 3, 3),
 (0, 2, 3, 3, 0),
 (0, 3, 3, 0, 2),
 (0, 3, 3, 2, 0),
 (2, 0, 0, 3, 3),
 (2, 0, 3, 3, 0),
 (2, 3, 3, 0, 0),
 (3, 3, 0, 0, 2),
 (3, 3, 0, 2, 0),
 (3, 3, 2, 0, 0)}

How to randomly permutate string without adjacent equal elements

Assuming you want an equal distribution of the valid permutations:
If you do not care about memory or runtime complexity, you can generate all permutations of the string (Generating all permutations of a given string), then remove all Strings which have adjacent same letters, and finally pick a random one from that list.

If you do care about optimizing memory or runtime, see the similar questions linked.

Some other approaches if you do not need an equal distribution, but still a chance for any valid permutation to be found:

You can build up the string by randomly picking from the remaining letters (similar as to what you did), and backtracking when you hit a dead end (no valid letter left to pick). See Python permutation using backtracking
You can make a string where you pick random letters from the input without caring about adjacent repetitions, and then swap-shuffle (see Heap's algorithm) this random starting point iteratively until the result matches your condition (or until you're back to the start).

Backtracking solution

Here I pick a random nextChar, and try to build a random String that does not start with that char. If that fails, try another one. By recursion, this eventually tries out all combinations in a random order, until a valid one is found.

private static final Random RANDOM = new Random();

public static void main(String[] args) {
    System.out.println(randomPerm("aaabcc"));
}

public static String randomPerm(String str) {
    Map<Character, Long> counts = str
            .chars()
            .mapToObj(c -> (char) c)
            .collect(groupingBy(Function.identity(), Collectors.counting()));
    return restPerm(null, counts);
}

public static String restPerm(Character previous, Map<Character, Long> leftover) {
    List<Character> leftKeys = new ArrayList<>(leftover.keySet());
    while (!leftKeys.isEmpty()) {
        Character nextChar = leftKeys.get(RANDOM.nextInt(leftKeys.size()));
        leftKeys.remove(nextChar);
        if (nextChar.equals(previous) || leftover.get(nextChar) == 0) {
            continue; // invalid next char
        }
        // modify map in place, reduce count by one
        Long count = leftover.compute(nextChar, (ch, co) -> co - 1);
        if (leftover.values().stream().noneMatch(c -> c > 0)) {
            return nextChar.toString();  // last char to use
        }
        String rest = restPerm(nextChar, leftover); // recurse
        if (rest != null) {
            return nextChar + rest; // solution found
        }
        leftover.put(nextChar, count + 1);
    }
    return null;
}

This solution will more likely find results where rare characters are used in the beginning of the result, so the distribution would not be equal. As an example input "aaaaaaabbbbbc" will have c more often on the left than on the right, like "acabababababa" in 50% of cases. But it uses limited memory and may complete before computing all permutations, and it is somewhat similar to your approach.

Generate all possible combinations of list using integer elements and their inverse

Make a list of the "inverse" and zip to get pairs, and use itertools product.

from itertools import product
lst = [1, 2, 3, 4]
inverse_lst = [-x for x in lst]
result = list(product(*zip(lst, inverse_lst)))

print(result)
[(1, 2, 3, 4),
 (1, 2, 3, -4),
 (1, 2, -3, 4),
 (1, 2, -3, -4),
 (1, -2, 3, 4),
 (1, -2, 3, -4),
 (1, -2, -3, 4),
 (1, -2, -3, -4),
 (-1, 2, 3, 4),
 (-1, 2, 3, -4),
 (-1, 2, -3, 4),
 (-1, 2, -3, -4),
 (-1, -2, 3, 4),
 (-1, -2, 3, -4),
 (-1, -2, -3, 4),
 (-1, -2, -3, -4)]

How to generate all permutations of a list but also add strings that can be present only once in any permutation

You have 3 series. The original input string as a list, and then you prepend and append. Generate those three separately:

from itertools import chain, product

inputstring = 'ABC'
extra = ['.', '%3A']
for combo in chain(inputstring, 
        product(extra, inputstring), product(inputstring, extra)):
    combo = ''.join(combo)
    print(combo)

Demo with a list comprehension:

>>> from itertools import chain, product
>>> inputstring = 'ABC'
>>> extra = ['.', '%3A']
>>> [''.join(combo) for combo in chain(inputstring, product(extra, inputstring), product(inputstring, extra))]
['A', 'B', 'C', '.A', '.B', '.C', '%3AA', '%3AB', '%3AC', 'A.', 'A%3A', 'B.', 'B%3A', 'C.', 'C%3A']

Given n, generate all permutations of size lesser than 0.5n

For your value "half of N" equal to 3 this would be:

using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))

Note that this is non-allocating so if you want to see the result collect is required:

julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [2, 3]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

Algorithm to generating all permutations of a string with no adjacent characters

Here’s a fairly straightforward backtracking solution pruning the search before adding an adjacent character to the permutation.

public class PermutationsNoAdjacent {

    private char[] inputChars;
    private boolean[] inputUsed;
    private char[] outputChars;
    private List<String> permutations = new ArrayList<>();

    public PermutationsNoAdjacent(String inputString) {
        inputChars = inputString.toCharArray();
        inputUsed = new boolean[inputString.length()];
        outputChars = new char[inputString.length()];
    }

    private String[] generatePermutations() {
        tryFirst();
        return permutations.toArray(new String[permutations.size()]);
    }

    private void tryFirst() {
        for (int inputIndex = 0; inputIndex < inputChars.length; inputIndex++) {
            assert !inputUsed[inputIndex] : inputIndex;
            outputChars[0] = inputChars[inputIndex];
            inputUsed[inputIndex] = true;
            tryNext(inputIndex, 1);
            inputUsed[inputIndex] = false;
        }
    }

    private void tryNext(int previousInputIndex, int outputIndex) {
        if (outputIndex == outputChars.length) { // done
            permutations.add(new String(outputChars));
        } else {
            // avoid previousInputIndex and adjecent indices
            for (int inputIndex = 0; inputIndex < previousInputIndex - 1; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
            for (int inputIndex = previousInputIndex + 2; inputIndex < inputChars.length; inputIndex++) {
                if (!inputUsed[inputIndex]) {
                    outputChars[outputIndex] = inputChars[inputIndex];
                    inputUsed[inputIndex] = true;
                    tryNext(inputIndex, outputIndex + 1);
                    inputUsed[inputIndex] = false;
                }
            }
        }
    }

    public static void main(String... args) {
        String[] permutations = new PermutationsNoAdjacent("ABCDEF").generatePermutations();
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }

}

It prints 90 permutations of ABCDEF. I’ll just quote the beginning and the end:

ACEBDF
ACEBFD
ACFDBE
ADBECF
…
FDBEAC
FDBECA

Generate All Permutations of a List Without Adjacent Equal Elements