#!/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)