The code takes too much time

Question

I wrote code to arrange numbers after user input. Ordering requires the sum of adjacent numbers to be simple. Up to 10 as input code works fine. If I go beyond this system, it freezes. Please let me know the steps to optimize it.

ex input 8
The answer should be: (1, 2, 3, 4, 7, 6, 5, 8)
The code is as follows.

import itertools x = raw_input("please enter a number") range_x = range(int(x)+1) del range_x[0] result = list(itertools.permutations(range_x)) def prime(x): for i in xrange(1,x,2): if i == 1: i = i+1 if x%i==0 and i < x : return False else: return True def is_prime(a): for i in xrange(len(a)): print a if i < len(a)-1: if prime(a[i]+a[i+1]): pass else: return False else: return True for i in xrange(len(result)): if i < len(result)-1: if is_prime(result[i]): print 'result is:' print result[i] break else: print 'result is' print result[i-1] 

Answer 1

Dynamic programming to the rescue:

 def is_prime(n): return all(n % i != 0 for i in range(2, n)) def order(numbers, current=[]): if not numbers: return current for i, n in enumerate(numbers): if current and not is_prime(n + current[-1]): continue result = order(numbers[:i] + numbers[i + 1:], current + [n]) if result: return result return False result = order(range(500)) for i in range(len(result) - 1): assert is_prime(result[i] + result[i + 1]) 

You can make it work even for larger lists by increasing the maximum recursion depth.

Answer 2

This answer is based on @Tim Peters assumption of Hamiltonian paths .

There are many possible solutions. To avoid excessive memory consumption for intermediate solutions, a random path may be generated. It also makes it easy to use multiple processors (each processor generates its own paths in parallel).

 import multiprocessing as mp import sys def main(): number = int(sys.argv[1]) # directed graph, vertices: 1..number (including ends) # there is an edge between i and j if (i+j) is prime vertices = range(1, number+1) G = {} # vertex -> adjacent vertices is_prime = sieve_of_eratosthenes(2*number+1) for i in vertices: G[i] = [] for j in vertices: if is_prime[i + j]: G[i].append(j) # there is an edge from i to j in the graph # utilize multiple cpus q = mp.Queue() for _ in range(mp.cpu_count()): p = mp.Process(target=hamiltonian_random, args=[G, q]) p.daemon = True # do not survive the main process p.start() print(q.get()) if __name__=="__main__": main() 

where is the Sieve of Eratosthenes :

 def sieve_of_eratosthenes(limit): is_prime = [True]*limit is_prime[0] = is_prime[1] = False # zero and one are not primes for n in range(int(limit**.5 + .5)): if is_prime[n]: for composite in range(n*n, limit, n): is_prime[composite] = False return is_prime 

and

 import random def hamiltonian_random(graph, result_queue): """Build random paths until Hamiltonian path is found.""" vertices = list(graph.keys()) while True: # build random path path = [random.choice(vertices)] # start with a random vertice while True: # until path can be extended with a random adjacent vertex neighbours = graph[path[-1]] random.shuffle(neighbours) for adjacent_vertex in neighbours: if adjacent_vertex not in path: path.append(adjacent_vertex) break else: # can't extend path break # check whether it is hamiltonian if len(path) == len(vertices): assert set(path) == set(vertices) result_queue.put(path) # found hamiltonian path return 

Example

 $ python order-adjacent-prime-sum.py 20 

Exit

 [19, 18, 13, 10, 1, 4, 9, 14, 5, 6, 17, 2, 15, 16, 7, 12, 11, 8, 3, 20] 

The output is a random sequence that satisfies the conditions:

• this is a permutation of the range from 1 to 20 (including)
• the sum of adjacent numbers is simple

Time performance

On average, to obtain the result for n = 900 it takes about 10 seconds and extrapolation of time as an exponential function, for n = 1000 it takes 20 seconds:

An image is created using this code:

 import numpy as np figname = 'hamiltonian_random_noset-noseq-900-900' Ns, Ts = np.loadtxt(figname+'.xy', unpack=True) # use polyfit to fit the data # y = c*a**n # log y = log (c * a ** n) # log Ts = log c + Ns * log a coeffs = np.polyfit(Ns, np.log2(Ts), deg=1) poly = np.poly1d(coeffs, variable='Ns') # use curve_fit to fit the data from scipy.optimize import curve_fit def func(x, a, c): return c*a**x popt, pcov = curve_fit(func, Ns, Ts) aa, cc = popt a, c = 2**coeffs # plot it import matplotlib.pyplot as plt plt.figure() plt.plot(Ns, np.log2(Ts), 'ko', label='time measurements') plt.plot(Ns, np.polyval(poly, Ns), 'r-', label=r'$time = %.2g\times %.4g^N$' % (c, a)) plt.plot(Ns, np.log2(func(Ns, *popt)), 'b-', label=r'$time = %.2g\times %.4g^N$' % (cc, aa)) plt.xlabel('N') plt.ylabel('log2(time in seconds)') plt.legend(loc='upper left') plt.show() 

Installed Values:

 >>> c*a**np.array([900, 1000]) array([ 11.37200806, 21.56029156]) >>> func([900, 1000], *popt) array([ 14.1521409 , 22.62916398]) 

Answer 3

For posterity ;-), here is another one based on finding the Hamiltonian path. This is Python3 code. As it is written, it stops when searching for the first path, but it is easy to change it to generate all paths. On my box, he finds a solution for all n from 1 to 900 inclusive in about one minute. For n , slightly greater than 900, it exceeds the maximum recursion depth.

The main generator ( psieve() ) is a huge excess for this particular problem, but I was comfortable and did not want to write another; -)

A path search ( ham() ) is a recursive backtracking search, using the often (but not always) very efficient ordering heuristics: of all the vertices adjacent to the last vertex of the path so far, first look at those with the smallest remaining output. For example, this is a “normal” heuristic used to solve Knights Tour problems. In this context, he often finds a tour without a return. Your problem looks a little more complicated.

 def psieve(): import itertools yield from (2, 3, 5, 7) D = {} ps = psieve() next(ps) p = next(ps) assert p == 3 psq = p*p for i in itertools.count(9, 2): if i in D: # composite step = D.pop(i) elif i < psq: # prime yield i continue else: # composite, = p*p assert i == psq step = 2*p p = next(ps) psq = p*p i += step while i in D: i += step D[i] = step def build_graph(n): primes = set() for p in psieve(): if p > 2*n: break else: primes.add(p) np1 = n+1 adj = [set() for i in range(np1)] for i in range(1, np1): for j in range(i+1, np1): if i+j in primes: adj[i].add(j) adj[j].add(i) return set(range(1, np1)), adj def ham(nodes, adj): class EarlyExit(Exception): pass def inner(index): if index == n: raise EarlyExit avail = adj[result[index-1]] if index else nodes for i in sorted(avail, key=lambda j: len(adj[j])): # Remove vertex i from the graph. If this isolates # more than 1 vertex, no path is possible. result[index] = i nodes.remove(i) nisolated = 0 for j in adj[i]: adj[j].remove(i) if not adj[j]: nisolated += 1 if nisolated > 1: break if nisolated < 2: inner(index + 1) nodes.add(i) for j in adj[i]: adj[j].add(i) n = len(nodes) result = [None] * n try: inner(0) except EarlyExit: return result def solve(n): nodes, adj = build_graph(n) return ham(nodes, adj) 

Answer 4

Here is my solution. As Tim Peters noted, this is a Hamiltonian path problem. So, the first step is to create a graph in some form.

Well, the zero step in this case is for generating prime numbers. I am going to use a sieve, but whatever the best test is. We need primes up to 2 * n , since this is the largest of the two numbers that can be summed.

 m = 8 n = m + 1 # Just so I don't have to worry about zero indexes and random +/- 1's primelen = 2 * m prime = [True] * primelen prime[0] = prime[1] = False for i in range(4, primelen, 2): prime[i] = False for i in range(3, primelen, 2): if not prime[i]: continue for j in range(i * i, primelen, i): prime[j] = False 

Ok, now we can check for primality with prime[i] . Now it's easy to make the edges of the graph. If I have the number i, then which numbers may appear next. I will also take advantage of the fact that I and j have the opposite parity.

 pairs = [set(j for j in range(i%2+1, n, 2) if prime[i+j]) for i in range(n)] 

So, here pairs[i] given an object whose elements are integers j such that i+j is prime.

Now we need to go through the schedule. This is indeed the place where time is required, and all further optimizations will be made here.

 chains = [ ([], set(range(1, n)) ] 

chains will track the actual paths as they progress. Your first result in the tuple. The second element is all unused numbers or invisible nodes. The idea is to pull one chain out of the queue, take a step down the path and return it.

 while chains: chain, unused = chains.pop() if not chain: # we haven't even started, all unused are valid valid_next = unused else: # We need numbers that are both unused and paired with the last node # Using sets makes this easy valid_next = unused & pairs[chains[-1]] for num in valid_next: # Take a step to the new node and add the new path back to chains # Reminder, its important not to mutate anything here, always make new objs newchain = chain + [num] newunused = unused - set([num]) chains.append( (newchain, newunused) ) # are we done? if not newunused: print newchain chains = False 

Please note that if there is no valid next step, the path will be deleted without replacement.

This is really inefficient, but works in a reasonable amount of time. The biggest performance bottleneck is walking on schedule, so the next optimization will appear and insert paths into smart places to prioritize the most likely paths. In this case, it would be useful to use collections.deque or another container for your chains.

EDIT

Here is an example of how you can realize your path priority. We will assign an account to each path and save a list of chains sorted by this account. For a simple example, I assume that paths containing "more complicated to use" nodes deserve more. That is, for each step along the path, the score will increase by n - len(valid_next) modified code will look something like this.

 import bisect chains = ... chains_score = [0] while chains: chain, unused = chains.pop() score = chains_score.pop() ... for num in valid_next: newchain = chain + [num] newunused = unused - set([num]) newscore = score + n - len(valid_next) index = bisect.bisect(chains_score, newscore) chains.insert(index, (newchain, newunused)) chains_score.insert(index, newscore) 

Remember that the insert is O(n) , so the overhead of adding this object can be quite large. It is worth doing some analysis on your evaluation algorithm to keep the length of the len(chains) queue manageable.