Reorder shuffled sequence of integers to match certain criteria (Codewars)

You can significantly increase your program's efficiency by directly iterating through the permutation generator.

The reason is because once the program finds a solution, it can break out of the loop, without having to iterate through more unnecessary permutations, like what storing them in a list does:

from itertools import permutations

def solve(arr):
    for p in permutations(arr, len(arr)):
        p = list(p)
        for ind, el in enumerate(p[:-1]):
            n1 = el/3
            if n1.is_integer():
                n1 = int(n1)
            n2 = el * 2

            if (n1 != p[ind+1]) and (n2 != p[ind+1]):
                break
        else:
            return p
print(solve([12, 3, 9, 4, 6, 8]) == [9, 3, 6, 12, 4, 8])

Output:

True

Looking through every possible permutation is absolutely the wrong way to solve this. If you're given 30 items, you'll never go through all 30! possibilities. There is a much simpler solution.

For each element of the array, find the next value:

my_sort = { a : a // 3 if a % 3  == 0 else 2 * a for a in arr}

Look though my_sort. You will find that there must be exactly one value in my_sort.keys() that isn't anywhere in my_sort.values(). This is your first key. You know this because each key must be the resulting value of some other key, except for the first one.

all_values = set(my_sort.values())
first_key = next(x for x in my_sort.keys() if x not in my_values)

Now just generate the list, starting from first_key.

The n! algorithm is now linear.

=== EDITED ===

This solution is incorrect. I misunderstood the algorithm. I thought that 12 had to be followed by 4, I didn't realize it could be followed by 4 or 24.

So for each element of the list, let's look at all its possible successors:

{12: [4, 24], 3: [1, 6], 9: {3, 18}, 4: [8], 6: [2, 12], 8: [16]}

Pruning the lists of successors to be those that are actually in the list:

{12: [4], 3: [6], 9: [3], 4: [8], 6: [12], 8: []}

At this point, it's clear that your list starts at 9 [nothing has 9 as a successor] and ends at 8 [it has nowhere to go]. You can just read off the answer as 9, 3, 6, 12, 4, 8.

It may turn out that all your test examples are this simple. Alternatively, there is a little bit more work if every element has a predecessor (you'll just have to try every possibility as the first item) or if some element has two possible successors, you'll have to check both of them. But your search space is now way smaller. You're only looking at the permutations that make sense, not all of them.

It may turn out that all of your tests are this simple.

I may be a bit late to this but seeing as you say you are looking for hints I will leave all the code within spoilers.

First of all, without going into any proofs,

because the only operations are Divide x by 3 and Multiply x by 2 and 2 and 3 are primes, once you perform one of these operations you can't return to the original integer, ever.

The only exception is 0. It isn't stated in the question but any input list containing 0 would just be a list of zeros. Let's assume 0 will never occur. You definitely can never reach zero using the two operations anyway.

In a sentence I'll say it's because all natural numbers can be expressed as a unique combination of prime factors. Look into prime factorisation for more.

This is very important because it means that no digit can appear twice in the sequence. meaning no loops, no repetition and most importantly, there is only one answer (ordered sequence).

Taking advantage of this, you can create a list of all possible pairs of elements.

import itertools
input = [12, 3, 9, 4, 6, 8]
# create all permutations of two numbers in the input list
pairs = [i for i in itertools.permutations(input, 2)]
print(pairs)

[(12, 3), (12, 9), (12, 4), (12, 6), (12, 8), (3, 12), (3, 9), (3, 4), (3, 6), (3, 8), (9, 12), (9, 3), (9, 4), (9, 6), (9, 8), (4, 12), (4, 3), (4, 9), (4, 6), (4, 8), (6, 12), (6, 3), (6, 9), (6, 4), (6, 8), (8, 12), (8, 3), (8, 9), (8, 4), (8, 6)]

Finding all permutations of two elements from a list isn't actually very slow. For example a list of 40 numbers would only generate 1600 unique pairs. Much fewer than the 1.2089258196e+64 permutations of all 40 numbers.

With these number pairs (a, b) we can discard any pairing that doesn't satisfy a / 3 = b or a * 2 = b

# remove any pairs (a,b) that aren't either a/3 = b or a*2 = b
correct_pairs = [(a,b) for (a,b) in pairs if a/3==b or a*2==b]

[(12, 4), (3, 6), (9, 3), (4, 8), (6, 12)]

All that is left over are the exact number of pairs for the exact number of operations needed in the sequence. All that is needed is to put them in order. This is the trickiest part.

Suggestion:

The easiest suggestion is to put these pairs (a,b) into a dictionary where a is the key and b the value of that key. This way looking up any key a gives a value b that points directly to the next key in the sequence.

All you have to do first is find the start of the sequence. Then you can just do an iterative search for the next number until you have the sequence.

Code:

a_b_dict = {a: b for (a,b) in correct_pairs}

# each pair is in form (a,b)
set_a = set([a for (a, b) in correct_pairs])

set_b = set([b for (a, b) in correct_pairs])

# subtract all numbers from the set of a that are in the set of b. The one number left over will be the start of the sequence
start_of_sequence = set(set_a - set_b).pop()


# add starting sequence number to new list
sorted_numbers = [start_of_sequence]

# remove starting number from dictionary and add the next number in sequence to list
sorted_numbers.append(a_b_dict.pop(start_of_sequence))

# empty dictionaries return False. Loop until a_b_dict is empty. The next key to lookup will be the last element of the current list (index = -1)
while a_b_dict:
sorted_numbers.append(a_b_dict.pop(sorted_numbers[-1]))

print(sorted_numbers)

Output:

[9, 3, 6, 12, 4, 8]