110 lines
2.7 KiB
Python
Executable File
110 lines
2.7 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
import time
|
|
from math import factorial
|
|
|
|
def shift(
|
|
number,
|
|
set_one_size,
|
|
set_two_size,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations):
|
|
|
|
for b in range(set_one_size):
|
|
if shiftIteration >= set_one_size:
|
|
return
|
|
number = number << 1
|
|
shiftIteration += 1
|
|
permutations.append(number)
|
|
subtractionValue = (subtractionValue << 1) + 1
|
|
subtract(
|
|
number,
|
|
set_one_size,
|
|
set_two_size,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations)
|
|
|
|
return
|
|
|
|
def subtract(
|
|
number,
|
|
set_one_size,
|
|
set_two_size,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations):
|
|
|
|
for b in range(set_two_size - 1):
|
|
if subtractionIteration >= set_two_size - 1:
|
|
return
|
|
number -= subtractionValue
|
|
subtractionIteration += 1
|
|
subtractionValue = subtractionValue << 1
|
|
permutations.append(number)
|
|
shift(
|
|
number,
|
|
set_one_size,
|
|
set_two_size,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations)
|
|
|
|
|
|
def run_algorithm(set_one, set_two):
|
|
|
|
num = 1
|
|
for x in range(1, set_two):
|
|
num = (num << 1) + 1
|
|
|
|
permutations = [num]
|
|
|
|
begin = time.clock()
|
|
|
|
shift(permutations[0], set_one, set_two, 0, 0, 0, permutations)
|
|
|
|
end = time.clock()
|
|
|
|
print("\nExecution Time: %f seconds" % (end - begin))
|
|
|
|
# permutations.sort(key=int)
|
|
|
|
# print permutations found (in decimal)
|
|
print()
|
|
print(permutations)
|
|
|
|
# caluclate info
|
|
perm_count = len(permutations)
|
|
expected_perms = (factorial(set_one + set_two) / (factorial(set_one) * factorial(set_two)))
|
|
duplicates = perm_count - len(set(permutations))
|
|
|
|
# print info
|
|
print()
|
|
print("Execution Time: %f seconds" % (end - begin))
|
|
print("Expected %d total permutations." % (expected_perms))
|
|
print("Found %d total permutations." % (perm_count))
|
|
print("Found %d duplicates\n" % (duplicates))
|
|
|
|
|
|
if __name__ == '__main__':
|
|
|
|
if len(sys.argv) != 3:
|
|
print(" Usage: ./algorithm4.py [set 1 count] [set 2 count]\n")
|
|
quit()
|
|
|
|
try:
|
|
set_one = int(sys.argv[1])
|
|
set_two = int(sys.argv[2])
|
|
except ValueError as e:
|
|
print("ERROR: invalid parameters. Please input numbers!")
|
|
print(" Usage: ./algorithm4.py [set 1 count] [set 2 count]\n")
|
|
quit()
|
|
|
|
run_algorithm(set_one, set_two)
|