Inspired by this: http://www.reddit.com/r/math/comments/dazw0/ask_mathit_permutations_with_pairwise_unique_sums/

shuffles.py

# shuffles.py
#
# Written for the following /r/math post:
#
# >  Hi all. I've got a programming problem that distills down to choosing
# >  a permutation, B, of a sequence A, with uniform probability such that
# >  no two pairwise sums are the same. For example:
# >  
# >      A = [ 0 1 2 3 4 ] 
# >      B = [ 2 4 1 3 0 ]
# >  A + B = [ 2 5 3 6 4 ]
# >  
# >  In this case the requirement is satisfied since there are no duplicate
# >  elements in A+B. If I'd swapped the last two elements in B, however,
# >  it would fail my criteria as the third and fourth places would both
# >  sum to 3.
# >  
# >  Is there some discrete math or point of view that I'm missing that
# >  might lead to a straightforward algorithm for efficiently generating
# >  B? It feels like there ought to be some simple twist on Fisher-Yates
# >  that would do it. (Either that or I'll find that some NP-complete
# >  problem reduces to it.) Thanks for any tips!
#
# http://www.reddit.com/r/math/comments/dazw0/ask_mathit_permutations_with_pairwise_unique_sums/  


# For the sake of argument, let's assume that we're starting with 
# A = [1, 2, ..., n], since any solution, B, to go with this can trivially 
# be converted to a solution for some other permutation of {1, ..., n}
#
# Similarly, any solution for [1, 2, ..., n] is also a solution for 
# [1 + k, 2 + k, ..., n + k] for some constant k.
#
# So, as long as we can generate solutions for [1, ..., n], we can generate
# solutions for any permutation of those elements, combined with any 
# constant factor added to them all.
#
# Also I've decided to call a "solution" for {1, ..., n} a "shuffle"

# The algorithm for generating solutions should be pretty readable, and 
# is the same as what a few commenters have already suggested.

# Also, I started out trying to write something "elegant", and then tried
# to turn it into something "readable", and now I feel like I've ended up
# with a mess which is neither. So it goes.

def shuffleIsValid(a, b=None):
    """
    Check if two given 'shuffles' are valid; i.e., if the element-wise
    sums are all distinct. If you don't pass a second parameter, then
    compare `a` to [1, 2, ..., n], where n = len(a)

    Check the lengths first, then sum each pair of elements, create a set, 
    and check that there are as many elements in it as there are in the
    original list (i.e., they're all distinct).
    """

    # Prepare default value for b, if necessary
    if not b: b = range(1, (len(a) + 1))

    return (len(a) == len(b)) \
        and (len(set([a[i] + b[i] for i in xrange(0, len(a))])) == len(a))

def generateShuffle(n, prohibited = [], push=[], derangements=True):
    """
    Recursively generate all the valid 'shuffles' of length `n`, assuming
    they're 'shuffles' against [1, 2, ..., n]. If `derangements` is True,
    we discard any 'shuffles' which aren't also complete derangements.
    
    Call initially with just a value for `n`
    """

    # k is the number of items we've already selected for, since we can't
    # have duplicates in the prohibited list
    #
    # Which also means, we're in the (k + 1)th slot
    k = len(prohibited)

    # Our choices for the next step are:
    #
    #   Start with the integers [1, ..., n]:
    #
    #   Remove ones we've already used:
    #
    #   Use the list of prohibited sums to remove all possible choices which
    #     would give us that sum. (i.e., the difference between the prohibited
    #     sum, and this slot, (k + 1)
    #
    #   Remove the value corresponding to the slot we're in, IF we're 
    #     forcing every "shuffle" to be a derangement).
    #
    # (These are sets to make the 'subtraction' simpler, without worrying
    #  about IndexErrors, trying to remove the same element more than once.)
    #
    choices = set(range(1, (n + 1)))
    choices -= set(push)
    choices -= set([(p - (k + 1)) for p in prohibited])
    if derangements:
        choices -= set([k + 1])
    
    # Start with no results
    results = []

    # We take each possibility for the next number...
    #
    # Then generate the possible remaining values, for that choice
    #   (We do this by recursing into generateShuffle again, amending 
    #   the lists of prohibited sums, and used values, accordingly.)
    # 
    # Then we check whether there *are* any possible remaining values,
    #   just in case we've hit a snag where it's impossible to continue
    #   with the values we've already chosen.
    #
    for x in choices:
        the_rest = generateShuffle(n, prohibited + [x + k + 1], push + [x], derangements)

        # Check there are more possibilities
        if the_rest:
            # Add them to the list of results
            for y in the_rest:
               results.append([x] + y)
        # Otherwise, if we have no possible values to continue with
        else:
            # If we're in the last place, then that's perfect, just return
            # our (only) possible value for this last slot
            if (n == (k + 1)):
                results.append([x])
            # Otherwise, we've hit a snag, and just return the empty list.

    return results


if __name__ == "__main__":
    # Some rudimentary tests
    print "\nChecking for derangement shuffles:"
    for n in range(3, 10):
        shuffles = generateShuffle(n)
        print "Checking n = %s, there are %s shuffles." % (n, len(shuffles))
        for shuffle in shuffles:
            if not shuffleIsValid(shuffle):
                print "Error: %s" % shuffle

    print "\nChecking for non-derangement shuffles:"
    for n in range(3, 10):
        shuffles = generateShuffle(n, derangements=False)
        print "Checking n = %s, there are %s shuffles." % (n, len(shuffles))
        for shuffle in shuffles:
            if not shuffleIsValid(shuffle):
                print "Error: %s" % shuffle

zzz_output.txt

Checking for derangement shuffles:
Checking n = 3, there are 2 shuffles.
Checking n = 4, there are 2 shuffles.
Checking n = 5, there are 6 shuffles.
Checking n = 6, there are 24 shuffles.
Checking n = 7, there are 132 shuffles.
Checking n = 8, there are 612 shuffles.
Checking n = 9, there are 3786 shuffles.

Checking for non-derangement shuffles:
Checking n = 3, there are 3 shuffles.
Checking n = 4, there are 7 shuffles.
Checking n = 5, there are 23 shuffles.
Checking n = 6, there are 83 shuffles.
Checking n = 7, there are 405 shuffles.
Checking n = 8, there are 2113 shuffles.
Checking n = 9, there are 12657 shuffles.