Listen mit bestimmten Eigenschaften effizient zählenPython

Python-Programme
Anonymous
 Listen mit bestimmten Eigenschaften effizient zählen

Post by Anonymous »

Mein Ziel ist es, Permutationen mit bestimmten Eigenschaften zu zählen. Ich erzeuge zunächst alle Permutationen und prüfe dann, ob die gewünschten Eigenschaften erfüllt sind. Wie könnte ich den Code verbessern, um mehr Permutationen aufzählen zu können? Ich bin derzeit in der Lage, Permutationen von 14 Elementen zu verarbeiten.
Bearbeiten: Befolgen Sie die Vorschläge von Jérôme Richard und attempt0, ich habe den Code umgestaltet, um Generatoren zu verwenden. Mache ich es richtig?

Code: Select all

from itertools import permutations

def check(seq, verbose=False):
"""check that the elements of the sequence equal a difference of previous elements"""
n = len(seq)
for k in range(1, n-1):
# build a set of admissible values
dk = {abs(seq[i]-seq[j]) for i in range(0, k) for j in range(i+1, k+1) if i < j}
if k > 0 and verbose:
print('current index = ', k)
print('current subsequence = ', seq[:k+1])
print('current admissible values = ', dk)
print('next element = ', seq[k+1])
# check if the next element is in the set of admissible values
if k > 0 and seq[k+1] not in dk:
# return an invalid subsequence (k+2 to include the invalid element)
return seq[:k+2]
return seq

def is_valid(seq):
"""check that the sequence satisfies certain properties"""
n = len(seq)
if n < 3:
return False
if len(check(seq)) == n:
return True
return False

def filter_perms(perms):
for perm in perms:
if is_valid(perm): yield perm

def make_perms(n):
"""The elements of the list are integers, where a list of length n stores all integers from 1 to n."""
for p in permutations(range(1,n-1)):
yield (n,) + p + (n-1,)

def enumerate_perms(n):
perms = make_perms(n)
return filter_perms(perms)

# testing a good sequence
seq=(5, 2, 3, 1, 4)
check(seq, verbose=True)
is_valid(seq)
# True

# testing a bad sequence
seq=[5, 2, 1, 3, 4]
check(seq, verbose=True)
is_valid(seq)
# False

# testing permutations
tuple(make_perms(5))

# testing enumeration
tuple(enumerate_perms(5))
# ((5, 2, 3, 1, 4), (5, 3, 2, 1, 4))

len(tuple(enumerate_perms(14)))
# 29340
Meine ersten Fragen (teilweise in den Kommentaren beantwortet): Sollte ich die Verwendung von Numpy-Arrays in Betracht ziehen? Sollte ich die Verwendung eines Generators in Betracht ziehen? Soll ich die Permutationen in einer Datenbank speichern?

Quick Reply

Change Text Case: 
   
  • Similar Topics
    Replies
    Views
    Last post