//Title: List Permutations
//Credit to: Kuraudo
//Contributed by: Kuraudo

/*
    The permutations() proc takes a list of elements to permutate. The return
    value is a list of [n!] lists, where each nested list contains [n] elements,
    and [n] is the number of elements in the list passed to permutations().

    For example: permutations( list(1,2) )
    Returns:    list(list(2,1), list(1,2))
*/

proc
    permutations(list/L)
        if(L.len > 1)
            var/list/result = list(list(L[2],L[1]), list(L[1],L[2]))
            
            for(var/i in 3 to L.len)
            
            // Duplicate each element [i] times:
                for(var/j=1, j<=result.len, j+=i)    
                    var/list/temp = result[j]
                    for(var/k=1, k<i, ++k)
                        result.Insert(j, 1)
                        result[j] = temp.Copy()
                
            // Insert L[i] into successive positions of each duplicate:
                for(var/j=1, j<=result.len, j+=i)
                    for(var/k=1, k<=i, ++k)
                        var/list/temp = result[j+k-1]
                        temp.Insert(k, L[i])

            return result
    
        else return list(list(L[1]))

///*
//Testing Code/Sample Implementation:

client/verb/Print(i as num)
    if(i && i>0)
        var/list/base = new
        for(var/j in 1 to i)
            base.Add(j)
            
        var/list/permutations = permutations(base)
        src << "Permutation of [i] [i==1?"element":"elements"]:"
        for(var/list/permutation in permutations)
            for(var/j=1, j<permutation.len, ++j)
                src << "[permutation[j]], \..."
            src << "[permutation[permutation.len]]"

//*/