🚀 go-pugleaf

In <1993Jan23.214452.26779@news.yale.edu> wayne@econ.yale.edu (Kevin Wayne) writes:

>I want to enumerate all combinations of n items taken p at a time for
>arbitrary n, p<=n.

>(i.e., for (n,p)=(5,3) generate a sequence of vectors:
>	[1 2 3], [1 2 4], [1 2 5], [1 3 4], [1 3 5], [1 4 5],
>	[2 3 4], [2 3 5], [2 4 5], [3 4 5] )

>Obviously, the computational effort will increase exponentially, but I only
>need to use it for relatively small n.

>If anyone has written such code, please send e-mail. Thanks in advance.

I have a function that converts between a cardinal number and an
associated combination.  This can be used to enumerate all such
combinations.  (I also have functions for permutations, if anyone is
interested.)  Use the following matlab code with the functions I provide
below:

n=5
p=3
l=choose(n,p)
U=1:n
P = card2comb(0:l-1, U, p)

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	card2comb.m
#	choose.m
# This archive created: Mon Jan 25 15:02:40 1993
export PATH; PATH=/bin:$PATH
echo shar: extracting "'card2comb.m'" '(876 characters)'
if test -f 'card2comb.m'
then
	echo shar: will not over-write existing file "'card2comb.m'"
else
sed 's/^XX//' << \SHAR_EOF > 'card2comb.m'
XXfunction P=card2comb(C,U,L)
XX
XX%CARD2COMB
XX%	P=card2comb(C,U,L) converts from a cardinal number representing a
XX%	combination of L elements of the set U into the combination itself.
XX%	The cardinal number is interpreted as the index (starting at 0)
XX%	into the sorted list of all possible combinations, with the
XX%	lexicographical order defined by the order of elements in U.
XX
XX%	Michael Maurer, 25 Jan 1993
XX%	Copyright (c) Michael Maurer, 1993.
XX
XXM=length(U);
XXN=length(C);
XXP=zeros(L,N);
XX
XXif any(C>=choose(M,L)),
XX   error('C too large to represent L-sample combination of U')
XXend
XXif L<1,
XX   error('L must be positive')
XXend
XX
XXfor i=1:N,
XX   Ci=C(i);
XX   if L>1,
XX      e=1;
XX      Ni=choose(M-e,L-1);
XX      while Ci+1>Ni,
XX	 Ci=Ci-Ni;
XX	 e=e+1;
XX	 Ni=choose(M-e,L-1);
XX      end
XX      P(1,i)=U(e);
XX      Ui=U(e+1:M);
XX      P(2:L,i)=card2comb(Ci,Ui,L-1);
XX   else
XX      P(1,i)=U(Ci+1);
XX   end
XXend
SHAR_EOF
if test 876 -ne "`wc -c < 'card2comb.m'`"
then
	echo shar: error transmitting "'card2comb.m'" '(should have been 876 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'choose.m'" '(443 characters)'
if test -f 'choose.m'
then
	echo shar: will not over-write existing file "'choose.m'"
else
sed 's/^XX//' << \SHAR_EOF > 'choose.m'
XXfunction a = choose(n,k)
XX%CHOOSE
XX%	a = choose(n,k) computes "n choose k", the number of ways of
XX%	choosing k objects from a pool of n objects, ignoring order.
XX%	Defined as
XX%			n!
XX%		    ----------
XX%		     k! (n-k)!
XX
XX%	Michael Maurer, Oct 26 1989
XX%	Copyright (c) Michael Maurer, 1993.
XX
XXif (length(n) ~= length(k)),
XX	error('n and k must be same length')
XXend
XX
XXa = zeroc(n);
XXfor i=1:length(n),
XX	a(i) = prod((n(i)-k(i)+1):n(i)) / prod(1:k(i));
XXend
SHAR_EOF
if test 443 -ne "`wc -c < 'choose.m'`"
then
	echo shar: error transmitting "'choose.m'" '(should have been 443 characters)'
fi
fi # end of overwriting check
#	End of shell archive
exit 0
--
______________________________________________________________________
Michael Maurer          maurer@nova.stanford.edu        (415) 723-1024