Welcome to Math Overflow

Question

1

I'm looking for a way of generating all permutations of three digits (actually xyz) that sum to the same value.

For example:

Ideally I need a way of mapping indices to the three digits in a unique way such that I can take an index up to the associated triangle number n * (n + 1) / 2 and find the same three indices every time.

Can anyone point me in the right direction? It's quite some time since I've worked with sequences and I'm a little rusty.

edited Dec 21 at 16:10

Michael Lugo
4,540●3●23

asked Dec 21 at 15:17

baileydan
21●1

	The 'generating-functions' tag is quite unrelated. – Mariano Suárez-Alvarez Dec 21 at 16:06
	I removed the generating-functions tag. – Michael Lugo Dec 21 at 16:11
	For enumeration problems of this kind it is often of interest to have the consecutive items in the list (including between the last and first) be "near each other." This type enumeration is called a "Gray code," for Frank Gray who carried out an enumeration of this kind for the binary sequences of length n. For the binary sequences the idea was to have consecutive sequences have Hamming distance 1 between them. So the Gray code for this case is a Hamiltonian circuit on the n-cube. – Joseph Malkevitch Dec 21 at 18:39

Steve Huntsman · Answer 1 · 2009-12-21 15:50:32Z UTC

3

The answer is detailed (along with MATLAB code) at

http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/

and successive posts. Use the MATLAB function "lookup" to produce the graded lex order.

answered Dec 21 at 15:50

Steve Huntsman
3,284●4●23

Greg Kuperberg · Answer 2 · 2009-12-21 18:09:12Z UTC

Your question is how to list the ways to multichoose the positions of $n$ balls in 3 boxes. You could more generally list the ways to multichoose the positions of $k$ balls in $n$ boxes.

The clearest theoretical answer is given by the "stars and bars" construction. Multiset coefficients and the stars and bars construction are explained very nicely in Wikipedia. Here is a Python code inspired by the stars-and-bars bijection between multiset choices and ordinary subset choices.

def multichoose(n,k):
    if k < 0 or n < 0: return "Error"
    if not k: return [[0]*n]
    if not n: return []
    if n == 1: return [[k]]
    return [[0]+val for val in multichoose(n-1,k)] + \
        [[val[0]+1]+val[1:] for val in multichoose(n,k-1)]

Evaluate multichoose(3,4) and see what you get!

Uniquely generate all permutations of three digits that sum to a particular value?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.