python: find all Latin Squares of a set (or partial square with fewer columns)
Question: EDIT:  
Thanks to commenter Douglas Zare, I have renamed the title of this post with
more appropriate terminology for anybody else who may be looking for something
similar. The code from David Eisenstat below was very helpful.

* * *

ORIGINAL POST:  
I apologize for the lack of appropriate set theory terminology... but I'm a
bit out of my depths here (though I suspect it's an easy problem). I'm trying
to develop an algorithm that will accept a set, and a number K, and return all
possible "complete" partitions with K-sized subsets and with set coverage=K
such that:  

  1. **any given subset will not have duplicates**
  2. **combining the nth term across all subsets gives a complete partition of the set**
  3. **the nth term of all subsets is unique across the rest of the subsets**

for example:  

    
    
    function({A, B, C, D}, 2)
    

should return all possible sets like this:  

    
    
    [AB, BC, CD, DA]
    [AB, BD, CA, DC]
    [AC, BD, CA, DB]
    [AD, DA, CB, BC]
    [BC, CA, DB, AD]
    ...
    

also, for what it's worth  

  4. **the order of the elements in an individual subset doesn't matter (as long as the other three rules are obeyed**

so the following are equivalent:

    
    
    [AB, BA, CD, DC] = [BA, AB, DC, CD] = [AB, BA, DC, CD] = [BA, AB, CD, DC]
    

and

  5. **order of the various subsets _does_ matter:**

so the following are different:

    
    
    [BC, CA, DB, AD] ≠ [CA, BC, AD, DB]
    

Put another way, in matrix terms: I'm looking for all matrices with
`rows=len(set)` and `columns=K` such every column has exact cover and no item
appears in any row more than once.

    
    
    function({A, B, C, D}, 3)
    

would return all matrices like the following...

    
    
    ABC      ADB    
    BCD      DCA    
    CDA      CBD    
    DAB      BAC 
    

I'm hoping for an answer in python, and using libraries like numpy is fine...
but just a general algorithmic strategy would be appreciated as well. I
thought something like [Algorithm
X](http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html) might come in
handy... but I've been unable to make the leap from that to the problem
outlined here...


Answer: Doable with a backtracking search. Python 3:

    
    
    import itertools
    import operator
    
    
    def valid(cols_so_far):
        for i, col1 in enumerate(cols_so_far):
            for col2 in cols_so_far[i + 1:]:
                if any(map(operator.eq, col1, col2)):
                    return False
        return True
    
    
    def enum(letters, k, cols_so_far=None):
        if cols_so_far is None:
            cols_so_far = (tuple(letters),)
        if not valid(cols_so_far):
            pass
        elif len(cols_so_far) == k:
            yield tuple(zip(*cols_so_far))  # transpose
        else:
            for perm in itertools.permutations(letters):
                yield from enum(letters, k, cols_so_far + (perm,))
    

