Combinations

From Rosetta Code

Given non-negative integers m and n, generate all size m combinations of the integers from 0 to n-1 in sorted order (each combination is sorted and the entire table is sorted).

For example, 3 comb 5 is

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

If it is more "natural" in your language to start counting from 1 instead of 0 the combinations can be of the integers from 1 to n.

Contents 1 Ada 2 D 3 E 4 Haskell 5 J 5.1 Iteration 5.2 Recursion 6 Java 7 JavaScript 8 Logo 9 OCaml 10 Perl 11 Pop11 12 Python 13 Scheme

[edit] Ada

 
with Ada.Text_IO;  use Ada.Text_IO;
 
procedure Test_Combinations is
   generic
      type Integers is range <>;
   package Combinations is
      type Combination is array (Positive range <>) of Integers;
      procedure First (X : in out Combination);
      procedure Next (X : in out Combination); 
      procedure Put (X : Combination);
   end Combinations;
 
   package body Combinations is
      procedure First (X : in out Combination) is
      begin
         X (1) := Integers'First;
         for I in 2..X'Last loop
            X (I) := X (I - 1) + 1;
         end loop;
      end First;
      procedure Next (X : in out Combination) is
      begin
         for I in reverse X'Range loop
            if X (I) < Integers'Val (Integers'Pos (Integers'Last) - X'Last + I) then
               X (I) := X (I) + 1;
               for J in I + 1..X'Last loop
                  X (J) := X (J - 1) + 1;
               end loop;
               return;
            end if;
         end loop;
         raise Constraint_Error;
      end Next;
      procedure Put (X : Combination) is
      begin
         for I in X'Range loop
            Put (Integers'Image (X (I)));
         end loop;
      end Put;
   end Combinations;
 
   type Five is range 0..4;
   package Fives is new Combinations (Five);
   use Fives;
 
   X : Combination (1..3);
begin
   First (X);
   loop
      Put (X); New_Line;
      Next (X);
   end loop;
exception
   when Constraint_Error =>
      null;
end Test_Combinations;
 

The solution is generic the formal parameter is the integer type to make combinations of. The type range determines n. In the example it is

 
type Five is range 0..4;
 

The parameter m is the object's constraint. When n < m the procedure First (selects the first combination) will propagate Constraint_Error. The procedure Next selects the next combination. Constraint_Error is propagated when it is the last one. Sample output:

 0 1 2
 0 1 3
 0 1 4
 0 2 3
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

[edit] D

Includes an algorithm to find mth Lexicographical Element of a Combination.

module combin ;
import std.stdio, std.format: fmx = format ;
 
struct Combin{
  const int n_, m_ ;
  int opApply(int delegate(inout int[]) dg) {
    int breaked = m_ < 0 || n_ < 0 ? 1 : 0  ;
    int combinate(int[] sel, int cur, int left) {
      if(breaked == 0) {
        if(left > 0)          
          for(int i = cur ; i + left <= n_ ; i++)
            combinate(sel ~ [i], i + 1, left - 1) ;
        else
          breaked = dg(sel) ;
      }
      return breaked ;
    }
    return combinate([], 0, m_) ;
  }
  string toString() { return fmx("%s",opSlice(0,length)) ; }
  size_t length() { return choose(n_, m_) ; }
 
  int[] opIndex(size_t idx) {
    ulong largestV(ulong p, ulong q, ulong r) {
      ulong v = p - 1 ;
      while(choose(v,q) > r) v-- ;
      return v ;
    }
    if(m_ < 0 || n_ < 0) return null ;
    if(idx >= length) throw new Exception("Out of bound") ;
    int[] result ;    
    ulong a = n_ , b = m_ , x = choose(n_,m_) - 1 - idx ;   
    for(ulong i = 0 ; i < m_; i++) {
      a = largestV(a, b, x) ;
      x = x - choose(a,b) ;
      b = b - 1 ;
      result ~= (n_ - 1 - a) ;
    }       
    return result ;   
  }
  int[][] opSlice(size_t a = 0, size_t b = size_t.max) {
    int[][] slice ;
    if(b == size_t.max) b = length ;
    for(size_t i = a; i < b ; i++) slice ~= opIndex(i) ; 
    return slice ;
  }
}
 
ulong choose(ulong n, ulong k) {
  if(n<0 || k < 0) throw new Exception("No negative") ;
  if(n < k) return 0 ;
  else if(n == k) return 1 ;
  ulong delta, iMax ;
  if(k < n - k) { delta = n - k ; iMax = k ; } 
  else { delta = k ; iMax = n - k ; }
  ulong ans = delta + 1 ;
  for(ulong i = 2 ; i <= iMax ; i++)
    ans = ans * (delta + i) / i ;
  return ans ;
}
 
void main() {
  foreach(c ; Combin(5,3))
    writefln(c) ; 
  auto cm = Combin(5,3) ;
  writefln("%s\n%s", typeid(typeof(cm)), cm) ;
  auto cp = cm[] ;    
  writefln("%s\n%s", typeid(typeof(cp)), cp) ;
  for(int i = 0 ; i< cm.length ; i++)
    writefln(cm[i]) ;
}

[edit] E

def combinations(m, range) {
  return if (m <=> 0) { [[]] } else {
    def combGenerator {
      to iterate(f) {
        for i in range {
          for suffix in combinations(m.previous(), range & (int > i)) {
            f(null, [i] + suffix)
          }
        }
      }
    }
  }
}

? for x in combinations(3, 0..4) { println(x) }

[edit] Haskell

It's more natural to extend the task to all (ordered) sublists of size m of a list.

Straightforward, unoptimized implementation with divide-and-conquer:

comb :: Int -> [a] -> [[a]]
comb 0 _      = [[]]
comb _ []     = []
comb m (x:xs) = map (x:) (comb (m-1) xs) ++ comb m xs

In the induction step, either x is not in the result and the recursion proceeds with the rest of the list xs, or it is in the result and then we only need m-1 elements.

To generate combinations of integers between 0 and n-1, use

comb0 m n = comb m [0..n-1]

Similar, for integers between 1 and n, use

comb1 m n = comb m [1..n]

[edit] J

[edit] Iteration

comb1=: 4 : 0
 c=. 1 {.~ - d=. 1+y-x
 z=. i.1 0
 for_j. (d-1+y)+/&i.d do. z=. (c#j) ,. z{~;(-c){.&.><i.{.c=. +/\.c end.
)

[edit] Recursion

comb=: 4 : 0 M.
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
)

The M. uses memoization which greatly reduces the running time.

[edit] Java

Translation of: JavaScript

Works with: Java version 1.5+

import java.util.Collections;
import java.util.LinkedList;
 
public class Comb{
 
        public static void main(String[] args){
                System.out.println(comb(3,5));
        }
 
        public static String bitprint(int u){
                String s= "";
                for(int n= 0;u > 0;++n, u>>= 1)
                        if((u & 1) > 0) s+= n + " ";
                return s;
        }
 
        public static int bitcount(int u){
                int n;
                for(n= 0;u > 0;++n, u&= (u - 1));
                return n;
        }
 
        public static LinkedList<String> comb(int c, int n){
                LinkedList<String> s= new LinkedList<String>();
                for(int u= 0;u < 1 << n;u++)
                        if(bitcount(u) == c) s.push(bitprint(u));
                Collections.sort(s);
                return s;
        }
}

[edit] JavaScript

function bitprint(u) {
  var s="";
  for (var n=0; u; ++n, u>>=1)
    if (u&1) s+=n+" ";
  return s;
}
function bitcount(u) {
  for (var n=0; u; ++n, u=u&(u-1));
  return n;
}
function comb(c,n) {
  var s=[];
  for (var u=0; u<1<<n; u++)
    if (bitcount(u)==c)
      s.push(bitprint(u))
  return s.sort();
}
comb(3,5)

[edit] Logo

to comb :n :list
  if :n = 0 [output [[]]]
  if empty? :list [output []]
  output sentence map [sentence first :list ?] comb :n-1 bf :list ~
                  comb :n bf :list
end
print comb 3 [0 1 2 3 4]

[edit] OCaml

Like the Haskell code:

let rec comb m lst =
  match m, lst with
    0, _ -> [[]]
  | _, [] -> []
  | m, x :: xs -> List.map (fun y -> x :: y) (comb (pred m) xs) @
                  comb m xs
;;
comb 3 [0;1;2;3;4];;

[edit] Perl

Library: Math::Combinatorics

use Math::Combinatorics;

@n = (0 .. 4);
print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n";

[edit] Pop11

Natural recursive solution: first we choose first number i and then we recursively generate all combinations of m - 1 numbers between i + 1 and n - 1. Main work is done in the internal 'do_combs' function, the outer 'comb' just sets up variable to accumulate results and reverses the final result.

The 'el_lst' parameter to 'do_combs' contains partial combination (list of numbers which were chosen in previous steps) in reverse order.

define comb(n, m);
    lvars ress = [];
    define do_combs(l, m, el_lst);
        lvars i;
        if m = 0 then
            cons(rev(el_lst), ress) -> ress;
        else
            for i from l to n - m do
                do_combs(i + 1, m - 1, cons(i, el_lst));
            endfor;
        endif;
    enddefine;
    do_combs(0, m, []);
    rev(ress);
enddefine;

comb(5, 3) ==>

[edit] Python

From the E code:

def comb(m, lst):
    if m == 0:
        return [[]]
    else:
        return [[x] + suffix for i, x in enumerate(lst)
                for suffix in comb(m - 1, lst[i + 1:])]

Example:

>>> comb(3, range(5))
[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

[edit] Scheme

Like the Haskell code:

(define (comb m lst)
  (cond ((= m 0) '(()))
        ((null? lst) '())
        (else (append (map (lambda (y) (cons (car lst) y))
                           (comb (- m 1) (cdr lst)))
                      (comb m (cdr lst))))))

(comb 3 '(0 1 2 3 4))