#!/usr/bin/env python
"""
LICENSE: Attribution Non-Commercial Share Alike
cc by-nc-sa
http://creativecommons.org/licenses/by-nc-sa/3.0

Attribution:  Scott Hendrickson  http://drskippy.net
"""

from copy import copy
import math

class Set:
    def __init__(self, data):
        """ Data can be map (uses keys) or list. Data must not have repeating elements
        (must be a set). """
        if type(data).__name__=='list':
            self.entities = data
        elif type(data).__name__=='dict':
            self.entities = data.keys()
        self.entities.sort()
    
    def getEntities(self):
        """ Entries list getter. """
        return self.entities
    
    def getSize(self):
        return len(self.entities)

    def sort(self):
        """ Sort entries in alphabetical order.  Returns sorted list. """
        self.entities.sort()
        return self.entities
  
    def partitionBySubSet(self, set):
        """ Given a set that is a subset of the entities, 
        return the set and the items in entries not in the
        set."""
        result = []
        for i in self.entities:
            if i not in set:
                result.append(i)
        return set, result
  
    def isEqual(self, a, b):
        """ Determine if a == b. Sorts the list to compare element
        by element. Does not alter a or b. """
        tmp1 = copy(a)
        tmp1.sort()
        tmp2 = copy(b)
        tmp2.sort()
        return tmp1 == tmp2
    
    def visit (self, a, b):
        """Return elements of a indexed by b.  Maximum value in b
        must be size(a) - 1."""
        result = []
        for idx in b:
            result.append(a[idx])
        return result
    
    def knuthAlgorithmT(self, t, data):
        """ n is the total number of elements.  This method generates
        all (lexicographic) t-combinations of the integers 1 to n. """
        result = []
        c = ['x']
        c += range(0,t)
        c.append(len(data))
        c.append(0)
        j = t
        while True:
            result.append(self.visit(data,c[1:-2]))
            if j>0:
                x = j
            else:
                if c[1] + 1 < c[2]:
                    c[1] += 1
                    continue
                else:
                    j = 2
                    c[j-1] = j-2
                    x = c[j] + 1
                    while x == c[j+1]:
                        j += 1
                        c[j-1] = j-2
                        x = c[j] + 1
                    if j > t:
                        break
            c[j] = x
            j -= 1      
        return result
        
    def recursiveAlgorithm(self, size, data):
        """ Recursive method to generate all of the unique sets of 
        size items from entities. """
        result = []
        if size == 1:
            return [[i] for i in data]
        elif size == 2:
            for i in range(0,len(data)):
                for j in range(i+1,len(data)):
                    tmp = [data[i], data[j]]
                    tmp.sort()
                    result.append(tmp)
            return result
        else:
            for k in range(0,len(data)-size + 1):
                subData = copy(data[k+1:])
                subResult = self.recursiveAlgorithm(size=size-1, data=subData)
                for a in subResult:
                    tmp = [data[k]] + a
                    tmp.sort()
                    result.append(tmp)
        return result
    
    def getCombinations1(self, size = 2, data=None):
        if data is None:
            data = self.entities
        return self.recursiveAlgorithm(size, data)
    
    def getCombinations2(self, size = 2, data = None):
        if data is None:
            data = self.entities
        return self.knuthAlgorithmT(size, data)
            
    def toString(self, d, sep="\n"):
        """ Convert list to string with separator (option: sep).
        Default is elements separated by newline. """
        result = ''
        if d is None:
            d = self.entities
        for row in d:
            result += str(row) + sep
        return result
    
    def factorial(self, n):
        """ Math lib in 2.6.  Recursive factorial function. """
        if n <= 1:
            return 1
        else:
            return n*self.factorial(n-1)
    
    def __str__(self):
        result = str(self.entities)
        return result
    
class SetPartitions:
    def __init__(self, set):
        self.set = set
        self.partitions = []
        
    def getPartitions(self):
        if self.partitions == []:
            self.knuthAlgorithmH()
        return self.partitions
        
    def visit(self, a, b):
        """Return elements of a with partition indexed by b.  Maximum value in b
        must be size(a) - 1."""
        result = {}
        entityIndex = 0
        for partitionIndex in b:
            if partitionIndex not in result:
                result[partitionIndex] = [a[entityIndex]]
            else:
                result[partitionIndex].append(a[entityIndex])
            entityIndex += 1
        return result.values()
        
    def knuthAlgorithmH(self, data = None):
        self.partitions = []
        if data is None:
            n = range(1,self.set.getSize()+1)
        else:
            n = range(1,len(data)+1)
        a = ['x'] + [0 for i in n]
        b = ['x'] + [1 for i in n[:-1]]
        m = 1
        while True:
            self.partitions.append(self.visit(self.set.getEntities(), a[1:]))
            if a[-1] == m:
                j = n[-1] - 1
                while a[j] == b[j]:
                    j -= 1
                if j == 1:
                    break
                else:
                    a[j] += 1
                m = b[j]
                if a[j] == b[j]:
                    m += 1
                j += 1
                while j < n[-1]:
                    a[j] = 0
                    b[j] = m
                    j += 1
                a[-1] = 0
            else:
                a[-1] += 1
        return self.partitions
           
    def getSize(self):
        if self.partitions == []:
            self.getPartitions()
        return len(self.partitions)
        
    def __str__(self):
        result = '<<<  %d Partitions  >>>\n'%self.getSize()
        result += '-'*40 + '\n'
        result += self.set.toString(self.getPartitions())
        return result
        
if __name__ == '__main__':

    data2 = ['a','b','c','d']
    data1 = ['a','b','c']
    
    s = Set(data2)
    print s
    p = SetPartitions(s)
    print p