fork download
copy 
  1. import itertools
  2. import re
  3. import string
  4. import time
  5.  
  6.  
  7. def is_valid(arrangement):
  8.     table = arrangement.lower()
  9.     return table[0] != table[-1] and not re.search(r'(\w)\1', table)
  10.  
  11.  
  12. def permutations(people, preset):
  13.     if preset is None:
  14.         preset = people[0] + '_' * (len(people) - 1)
  15.     unused = [person for person in people if person not in preset]
  16.     cases = itertools.permutations(unused)
  17.     template = preset.replace('_', '{}')
  18.     return (template.format(*p) for p in cases)
  19.  
  20.  
  21. def get_valid_seatings(people, preset=None):
  22.     if preset is None:
  23.         preset = people[0] + '_' * (len(people) - 1)
  24.     cases = permutations(people, preset)
  25.     return [c for c in cases if is_valid(c)]
  26.  
  27.  
  28. def count_seatings(num_couples):
  29.     people = string.ascii_lowercase[:num_couples] + string.ascii_uppercase[:num_couples]
  30.     return len(get_valid_seatings(people))
  31.  
  32.  
  33. for i in range(1, 6):
  34.     start = time.time()
  35.     seatings = count_seatings(i)
  36.     end = time.time()
  37.     print('{} couples: {} -- {:0.3f}s'.format(i, seatings, end - start))
  38. # Try one with pre-seatings
  39. couples = 'abcdeABCDE'
  40. impatient = 'a__bc__A__'
  41. start = time.time()
  42. seatings = len(get_valid_seatings(couples, impatient))
  43. end = time.time()
  44. print('4 impatient people: {} -- {:0.3f}s'.format(seatings, end - start))
Success #stdin #stdout 0.62s 10392KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
1 couples: 0 -- 0.000s
2 couples: 2 -- 0.000s
3 couples: 32 -- 0.000s
4 couples: 1488 -- 0.008s
5 couples: 112512 -- 0.592s
4 impatient people: 336 -- 0.001s
https://ideone.com/NM09Bh
language:
Python 3 (python  3.12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!