home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / softsys / matlab / 163 < prev    next >
Encoding:
Text File  |  1993-01-25  |  3.9 KB  |  136 lines
  1. Newsgroups: comp.soft-sys.matlab
  2. Path: sparky!uunet!stanford.edu!nntp.Stanford.EDU!forsythe.stanford.edu!nova!maurer
  3. From: Michael Maurer <maurer@nova.stanford.edu>
  4. Subject: Re: Enumerating Combinations
  5. Message-ID: <maurer.727998916@nova.Stanford.EDU>
  6. Sender: news@leland.Stanford.EDU (Mr News)
  7. Organization: STAR Lab, Stanford University, California USA
  8. References: <1993Jan23.214452.26779@news.yale.edu>
  9. Date: 25 Jan 93 21:55:16 GMT
  10. Lines: 124
  11.  
  12. In <1993Jan23.214452.26779@news.yale.edu> wayne@econ.yale.edu (Kevin Wayne) writes:
  13.  
  14. >I want to enumerate all combinations of n items taken p at a time for
  15. >arbitrary n, p<=n.
  16.  
  17. >(i.e., for (n,p)=(5,3) generate a sequence of vectors:
  18. >    [1 2 3], [1 2 4], [1 2 5], [1 3 4], [1 3 5], [1 4 5],
  19. >    [2 3 4], [2 3 5], [2 4 5], [3 4 5] )
  20.  
  21. >Obviously, the computational effort will increase exponentially, but I only
  22. >need to use it for relatively small n.
  23.  
  24. >If anyone has written such code, please send e-mail. Thanks in advance.
  25.  
  26. I have a function that converts between a cardinal number and an
  27. associated combination.  This can be used to enumerate all such
  28. combinations.  (I also have functions for permutations, if anyone is
  29. interested.)  Use the following matlab code with the functions I provide
  30. below:
  31.  
  32. n=5
  33. p=3
  34. l=choose(n,p)
  35. U=1:n
  36. P = card2comb(0:l-1, U, p)
  37.  
  38. #! /bin/sh
  39. # This is a shell archive, meaning:
  40. # 1. Remove everything above the #! /bin/sh line.
  41. # 2. Save the resulting text in a file.
  42. # 3. Execute the file with /bin/sh (not csh) to create the files:
  43. #    card2comb.m
  44. #    choose.m
  45. # This archive created: Mon Jan 25 15:02:40 1993
  46. export PATH; PATH=/bin:$PATH
  47. echo shar: extracting "'card2comb.m'" '(876 characters)'
  48. if test -f 'card2comb.m'
  49. then
  50.     echo shar: will not over-write existing file "'card2comb.m'"
  51. else
  52. sed 's/^XX//' << \SHAR_EOF > 'card2comb.m'
  53. XXfunction P=card2comb(C,U,L)
  54. XX
  55. XX%CARD2COMB
  56. XX%    P=card2comb(C,U,L) converts from a cardinal number representing a
  57. XX%    combination of L elements of the set U into the combination itself.
  58. XX%    The cardinal number is interpreted as the index (starting at 0)
  59. XX%    into the sorted list of all possible combinations, with the
  60. XX%    lexicographical order defined by the order of elements in U.
  61. XX
  62. XX%    Michael Maurer, 25 Jan 1993
  63. XX%    Copyright (c) Michael Maurer, 1993.
  64. XX
  65. XXM=length(U);
  66. XXN=length(C);
  67. XXP=zeros(L,N);
  68. XX
  69. XXif any(C>=choose(M,L)),
  70. XX   error('C too large to represent L-sample combination of U')
  71. XXend
  72. XXif L<1,
  73. XX   error('L must be positive')
  74. XXend
  75. XX
  76. XXfor i=1:N,
  77. XX   Ci=C(i);
  78. XX   if L>1,
  79. XX      e=1;
  80. XX      Ni=choose(M-e,L-1);
  81. XX      while Ci+1>Ni,
  82. XX     Ci=Ci-Ni;
  83. XX     e=e+1;
  84. XX     Ni=choose(M-e,L-1);
  85. XX      end
  86. XX      P(1,i)=U(e);
  87. XX      Ui=U(e+1:M);
  88. XX      P(2:L,i)=card2comb(Ci,Ui,L-1);
  89. XX   else
  90. XX      P(1,i)=U(Ci+1);
  91. XX   end
  92. XXend
  93. SHAR_EOF
  94. if test 876 -ne "`wc -c < 'card2comb.m'`"
  95. then
  96.     echo shar: error transmitting "'card2comb.m'" '(should have been 876 characters)'
  97. fi
  98. fi # end of overwriting check
  99. echo shar: extracting "'choose.m'" '(443 characters)'
  100. if test -f 'choose.m'
  101. then
  102.     echo shar: will not over-write existing file "'choose.m'"
  103. else
  104. sed 's/^XX//' << \SHAR_EOF > 'choose.m'
  105. XXfunction a = choose(n,k)
  106. XX%CHOOSE
  107. XX%    a = choose(n,k) computes "n choose k", the number of ways of
  108. XX%    choosing k objects from a pool of n objects, ignoring order.
  109. XX%    Defined as
  110. XX%            n!
  111. XX%            ----------
  112. XX%             k! (n-k)!
  113. XX
  114. XX%    Michael Maurer, Oct 26 1989
  115. XX%    Copyright (c) Michael Maurer, 1993.
  116. XX
  117. XXif (length(n) ~= length(k)),
  118. XX    error('n and k must be same length')
  119. XXend
  120. XX
  121. XXa = zeroc(n);
  122. XXfor i=1:length(n),
  123. XX    a(i) = prod((n(i)-k(i)+1):n(i)) / prod(1:k(i));
  124. XXend
  125. SHAR_EOF
  126. if test 443 -ne "`wc -c < 'choose.m'`"
  127. then
  128.     echo shar: error transmitting "'choose.m'" '(should have been 443 characters)'
  129. fi
  130. fi # end of overwriting check
  131. #    End of shell archive
  132. exit 0
  133. --
  134. ______________________________________________________________________
  135. Michael Maurer          maurer@nova.stanford.edu        (415) 723-1024
  136.