Combinations: Difference between revisions

=={{header|11l}}==

{{trans|D}}

I k == 0

R [[Int]()]

R result

 

{{out}}

<pre>

For maximum compatibility, this program uses only the basic instruction set (S/360)

and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.

COMBINE CSECT

USING COMBINE,R13 base register

PG DC CL92' ' buffer

YREGS

{{out}}

<pre>

2 4 5

3 4 5

</pre>

 

=={{header|Action!}}==

BYTE i

 

PROC Main()

Comb(5,3)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Combinations.png Screenshot from Atari 8-bit computer]

 

=={{header|Ada}}==

 

procedure Test_Combinations is

when Constraint_Error =>

null;

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

The parameter ''m'' is the object's constraint.

When ''n'' < ''m'' the procedure First (selects the first combination) will propagate Constraint_Error.

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

COMMENT REQUIRED BY "prelude_combinations_generative.a68"

);

 

# -*- coding: utf-8 -*- #

 

# OD # ))

)

{{out}}

<pre>

===Iteration===

 

set c to {}

repeat with i from 1 to k

end next_comb

 

{{out}}

 

===Functional composition===

{{Trans|JavaScript}}

 

-- comb :: Int -> [a] -> [[a]]

on unwords(xs)

intercalate(space, xs)

{{Out}}

<pre>0 1 2

1 3 4

2 3 4</pre>

 

=={{header|AutoHotkey}}==

contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276224.html#276224 forum]

MsgBox % Comb(3,3)

MsgBox % Comb(3,2)

c%j% += 1

}

 

=={{header|AWK}}==

## Default values for r and n (Choose 3 from pool of 5). Can

## alternatively be set on the command line:-

if (i < r) printf A[i] OFS

else print A[i]}}

 

Usage:

3 4 5

</pre>

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

sort% = FN_sortinit(0,0)

DEF FNfact(N%)

IF N%<=1 THEN = 1 ELSE = N%*FNfact(N%-1)

 

=={{header|Bracmat}}==

The program first constructs a pattern with <code>m</code> variables and an expression that evaluates <code>m</code> variables into a combination.

When all combinations are found, the pattern fails and we are in the rhs of the last <code>|</code> operator.

 

bvar combination combinations list m n pat pvar var

. !arg:(?m.?n)

' (!n+-1:~<0:?n&!n !list:?list)

& !list:!pat

comb$(3.5)

 

=={{header|C}}==

 

/* Type marker stick: using bits to indicate what's chosen. The stick can't

comb(5, 3, 0, 0);

return 0;

 

===Lexicographic ordered generation===

Without recursions, generate all combinations in sequence. Basic logic: put n items in the first n of m slots; each step, if right most slot can be moved one slot further right, do so; otherwise

find right most item that can be moved, move it one step and put all items already to its right next to it.

 

void comb(int m, int n, unsigned char *c)

comb(5, 3, buf);

return 0;

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

 

}

}

 

Here is another implementation that uses recursion, intead of an explicit stack:

 

using System;

using System.Collections.Generic;

}

}

 

 

 

Recursive version

class Combinations

{

}

}

 

=={{header|C++}}==

#include <iostream>

#include <string>

{

comb(5, 3);

{{out}}

<pre>

 

=={{header|Clojure}}==

"If m=1, generate a nested list of numbers [0,n)

If m>1, for each x in [0,n), and for each list in the recursion on [x+1,n), cons the two"

(doseq [n line]

(printf "%s " n))

 

The below code do not comply to the task described above. However, the combinations of n elements taken from m elements might be more natural to be expressed as a set of unordered sets of elements in Clojure using its Set data structure.

 

(defn combinations

"Generate the combinations of n elements from a list of [0..m)"

:when (not-any? #{x} r)]

(conj r x))))))))

 

=={{header|CLU}}==

combinations = iter (m, n: int) yields (sequence[int])

if m<=n then

stream$putl(po, "")

end

{{out}}

<pre>0 1 2

=={{header|CoffeeScript}}==

Basic backtracking solution.

combinations = (n, p) ->

return [ [] ] if p == 0

console.log combo

 

{{out}}

 

=={{header|Common Lisp}}==

"Call fn with each m combination of the integers from 0 to n-1 as a list. The list may be destroyed after fn returns."

(let ((combination (make-list m)))

(mc (1+ curr) (1- left) (1- needed) (rest comb-tail))

(mc (1+ curr) (1- left) needed comb-tail)))))

 

{{out}}Example use

 

=== Recursive method ===

(labels ((comb1 (l c m)

(when (>= (length l) m)

(comb1 list nil m)))

 

 

=== Alternate, iterative method ===

(let ((k (length a)) m)

(loop for i from 1 do

(1 2 4 5)

(1 3 4 5)

 

=={{header|Crystal}}==

def comb(m, n)

(0...n).to_a.each_combination(m) { |p| puts(p) }

end

 

[0, 1, 2]

[0, 1, 3]

[1, 3, 4]

[2, 3, 4]

 

=={{header|D}}==

===Slow Recursive Version===

{{trans|Python}}

if (k == 0) return [[]];

typeof(return) result;

import std.stdio;

[0, 1, 2, 3].comb(2).writeln;

{{out}}

<pre>[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]</pre>

{{trans|Haskell}}

Same output.

 

immutable(int)[][] comb(immutable int[] s, in int m) pure nothrow @safe {

void main() {

4.iota.array.comb(2).writeln;

 

===Lazy Version===

 

import std.traits: Unqual;

[1, 2, 3, 4].combinations!true(2).array.writeln;

[1, 2, 3, 4].combinations(2).map!(x => x).writeln;

 

===Lazy Lexicographical Combinations===

Includes an algorithm to find [http://msdn.microsoft.com/en-us/library/aa289166.aspx#mth_lexicograp_topic3 mth Lexicographical Element of a Combination].

import std.stdio, std.algorithm, std.conv;

 

foreach (c; Comb.On([1, 2, 3], 2))

writeln(c);

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/Combinations#Pascal Pascal].

=={{header|E}}==

return if (m <=> 0) { [[]] } else {

def combGenerator {

}

}

 

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

=={{header|EasyLang}}==

{{trans|Julia}}

m = 3

len result[] m

#

.

{{out}}

<pre>

[ 1 2 3 ]

[ 1 2 4 ]

[ 1 3 4 ]

[ 2 3 4 ]

</pre>

 

=={{header|EchoLisp}}==

;;

;; using the native (combinations) function

(combine (iota 5) 3)

→ ((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))

 

=={{header|Egison}}==

 

(define $comb

(lambda [$n $xs]

 

(test (comb 3 (between 0 4)))

{{out}}

<pre>

=={{header|Eiffel}}==

The core of the program is the recursive feature solve, which returns all possible strings of length n with k "ones" and n-k "zeros". The strings are then evaluated, each resulting in k corresponding integers for the digits where ones are found.

 

class

 

end

Test:

class

APPLICATION

end

 

{{out}}

<pre>

 

=={{header|Elena}}==

import extensions;

import extensions'routines;

Numbers(n)

{

}

 

{

var numbers := Numbers(N);

{

console.printLine(row.toString())

console.readChar()

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def comb(0, _), do: [[]]

def comb(_, []), do: []

{m, n} = {3, 5}

list = for i <- 1..n, do: i

 

{{out}}

=={{header|Emacs Lisp}}==

{{trans|Haskell}}

(cond ((zerop m) '(()))

((= n-max n) '())

(comb-recurse m 0 n))

 

 

{{out}}

=={{header|Erlang}}==

 

-module(comb).

-compile(export_all).

comb(N,[H|T]) ->

[[H|L] || L <- comb(N-1,T)]++comb(N,T).

 

===Dynamic Programming===

Could be optimized with a custom <code>zipwith/3</code> function instead of using <code>lists:sublist/2</code>.

 

-module(comb).

-export([combinations/2]).

lists:zipwith(fun lists:append/2, Step, Next)

end, [[[]]] ++ lists:duplicate(K, []), List).

 

=={{header|ERRE}}==

PROGRAM COMBINATIONS

 

GENERATE(1)

END PROGRAM

{{out}}

<pre>

 

=={{header|F_Sharp|F#}}==

let rec fC prefix m from = seq {

let rec loopFor f = seq {

choose 3 5

|> Seq.iter (printfn "%A")

{{out}}

<pre>[0; 1; 2]

 

=={{header|Factor}}==

 

<pre>

{

</pre>

This works with any kind of sequence:

<pre>{ { "a" "b" } { "a" "c" } { "b" "c" } }</pre>

 

=={{header|Fortran}}==

use iso_fortran_env

implicit none

end subroutine comb

 

Alternatively:

 

implicit none

end subroutine gen

 

{{out}}

<pre>1 2 3

This is remarkably compact and elegant.

 

byval stp as uinteger, byval depth as uinteger )

dim as uinteger i

input "Enter n comb m. ", n, m

dim as string outstr = ""

{{out}}

<pre>Enter n comb m. 3,5

 

=={{header|GAP}}==

Combinations([1 .. n], m);

 

Combinations([1 .. 5], 3);

# [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ],

 

=={{header|Glee}}==

 

$$(5!3) give all combinations of 3 out of 5

$$(>>>) sorted up,

 

Result:

 

1 2 3

1 2 4

2 3 5

2 4 5

 

=={{header|Go}}==

 

import (

}

rc(0, 0)

{{out}}

<pre>[0 1 2]

===In General===

A recursive closure must be ''pre-declared''.

comb = { m, list ->

def n = list.size()

newlist += comb(m-1, sublist).collect { [list[k]] + it }

}

 

Test program:

println "Choose from ${csny}"

 

{{out}}

 

===Zero-based Integers===

 

Test program:

 

{{out}}

 

===One-based Integers===

 

Test program:

 

{{out}}

 

Straightforward, unoptimized implementation with divide-and-conquer:

comb 0 _ = [[]]

comb _ [] = []

 

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.

 

Shorter version of the above:

 

comb :: Int -> [a] -> [[a]]

comb 0 _ = [[]]

 

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

 

 

Similar, for integers between 1 and ''n'', use

 

 

Another method is to use the built in ''Data.List.subsequences'' function, filter for subsequences of length ''m'' and then sort:

 

 

And yet another way is to use the list monad to generate all possible subsets:

 

 

===Dynamic Programming===

The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, <code>comb m (x1:x2:xs)</code> involves computing <code>comb (m-1) (x2:xs)</code> and <code>comb m (x2:xs)</code>, both of which (separately) compute <code>comb (m-1) xs</code>. To avoid repeated computation, we can use dynamic programming:

 

comb m xs = combsBySize xs !! m

where

 

main :: IO ()

{{Out}}

<pre>[[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]]</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

return combinations(3,5,0)

end

end

 

 

The {{libheader|Icon Programming Library}} provides the core procedure [http://www.cs.arizona.edu/icon/library/src/procs/lists.icn lcomb in lists] written by Ralph E. Griswold and Richard L. Goerwitz.

local j

 

else [L[j := 1 to *L - i + 1]] ||| lcomb(L[j + 1:0],i - 1)

 

{{out}}

<pre>3 combinations of 5 integers starting from 0

[ 1 3 4 ]

[ 2 3 4 ]</pre>

 

=={{header|J}}==

===Library===

 

 

Example use:

 

0 1 2

0 1 3

1 2 4

1 3 4

 

All implementations here give that same result if given the same arguments.

 

===Iteration===

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.

 

another iteration version

d =. 1 + y - x

k =. >: |. i. d

end.

;{.z

 

===Recursion===

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

The <code>M.</code> uses memoization (caching) which greatly reduces the running time. As a result, this is probably the fastest of the implementations here.

 

A less efficient but easier to understand recursion (similar to Python and Haskell).

if.(x=#y) +. x=1 do.

y

end.

)

You need to supply the "list" for example <code>i.5</code>

<code>

===Brute Force===

We can also generate all permutations and exclude those which are not properly sorted combinations. This is inefficient, but efficiency is not always important.

 

=={{header|Java}}==

 

{{works with|Java|1.5+}}

import java.util.LinkedList;

 

return s;

}

 

=={{header|JavaScript}}==

===Imperative===

 

var s="";

for (var n=0; u; ++n, u>>=1)

return s.sort();

}

 

Alternative recursive version using and an array of values instead of length:

{{trans|Python}}

 

var i,

subI,

combinations(["Crosby", "Stills", "Nash", "Young"], 3);

// produces: [["Crosby", "Stills", "Nash"], ["Crosby", "Stills", "Young"], ["Crosby", "Nash", "Young"], ["Stills", "Nash", "Young"]]

 

===Functional===

Simple recursion:

 

 

function comb(n, lst) {

}).join('\n');

 

 

We can significantly improve on the performance of the simple recursive function by deriving a memoized version of it, which stores intermediate results for repeated use.

 

 

// n -> [a] -> [[a]]

}).join('\n');

 

 

 

{{Out}}

 

0 1 3

0 1 4

1 2 4

1 3 4

 

 

====ES6====

Defined in terms of a recursive helper function:

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4],

 

Or, defining combinations in terms of a more general subsequences function:

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>[[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]]</pre>

 

With recursions:

if (prefix.length == 0) arr = [...Array(arr).keys()];

if (k == 0) return [prefix];

combinations(k - 1, arr.slice(i + 1), [...prefix, v])

);

 

=={{header|jq}}==

combination(r) generates a stream of combinations of the input array.

The stream can be captured in an array as shown in the second example.

if r > length or r < 0 then empty

elif r == length then .

 

# select r integers from the set (0 .. n-1)

'''Example 1'''

combinations(5;3)

=={{header|Julia}}==

The <code>combinations</code> function in the <code>Combinatorics.jl</code> package generates an iterable sequence of the combinations that you can loop over. (Note that the combinations are computed on the fly during the loop iteration, and are not pre-computed or stored since there many be a very large number of them.)

n = 4

m = 3

for i in combinations(0:n,m)

println(i')

{{out}}

<pre>[0 1 2]

 

If, on the other hand we wanted to show how it could be done in Julia, this recursive solution shows some potentials of Julia lang.

# COMBINATIONS OF 3 OUT OF 5 #

##############################

 

combinations(1, 0)

{{out}}

<pre>

[3, 4, 5]

</pre>

 

=={{header|K}}==

Recursive implementation:

 

f:{:[k=#x; :,x; :,/_f' x,'(1+*|x) _ !n]}

:,/f' !n

 

=={{header|Lambdatalk}}==

Translation from Emacs-lisp

 

{def comb

[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

 

 

=={{header|Kotlin}}==

===Recursion===

{{trans|Pascal}}

private val combination = IntArray(m)

 

fun main(args: Array<String>) {

Combinations(3, 5)

 

{{out}}

===Lazy===

{{trans|C#}}

 

inline fun <reified T> combinations(arr: Array<T>, m: Int) = sequence {

combinations((1..n).toList().toTypedArray(), m).forEach { println(it.joinToString(separator = " ")) }

}

 

{{out}}

=={{header|Lobster}}==

{{trans|Nim}}

 

// combi is an itertor that solves the Combinations problem for iota arrays as stated

i += 1

 

{{out}}

<pre>[0, 1, 2]

 

{{trans|JavaScript}}

 

// comba solves the general problem for any values in an input array

var s = ""

combi(4, 3): s += (map(_) i: ["Crosby", "Stills", "Nash", "Young"][i]) + " "

{{out}}

<pre>[[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]]

 

=={{header|Logo}}==

if :n = 0 [output [[]]]

if empty? :list [output []]

comb :n bf :list

end

 

=={{header|Lua}}==

function map(f, a, ...) if a then return f(a), map(f, ...) end end

function incr(k) return function(a) return k > a and a or a+1 end end

 

for k, v in ipairs(combs(3, 5)) do print(unpack(v)) end

 

=={{header|M2000 Interpreter}}==

Including a helper sub to export result to clipboard through a global variable (a temporary global variable)

Module Checkit {

Global a$

}

Checkit

{{out}}

<pre>

 

===Step by Step===

Module StepByStep {

Function CombinationsStep (a, nn) {

}

StepByStep

 

=={{header|M4}}==

define(`set',`define(`$1[$2]',`$3')')

define(`get',`defn(`$1[$2]')')

divert

 

 

=={{header|Maple}}==

This is built-in in Maple:

[[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]]

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

built-in function example

 

=={{header|MATLAB}}==

 

Task Solution:

 

ans =

1 2 4

1 3 4

 

=={{header|Maxima}}==

[a: copylist(a), i: p],

if a[1] + p = n + 1 then return(und),

[2, 3, 5],

[2, 4, 5],

 

=={{header|Modula-2}}==

{{trans|Pascal}}

{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}

MODULE Combinations;

FROM STextIO IMPORT

Generate(1);

END Combinations.

{{out}}

<pre>

 

=={{header|Nim}}==

var c = newSeq[int](n)

for i in 0 ..< n: c[i] = i

 

for i in comb(5, 3):

{{out}}

<pre>@[0, 1, 2]

 

Another way, using a stack. Adapted from C#:

 

var result = newSeq[int](n)

for i in combinations(5, 3):

 

=={{header|OCaml}}==

let rec c = function

| (0,_) -> [[]]

| hd :: tl -> print_int hd ; print_string " "; print_list tl

in List.iter print_list (combinations 3 5)

 

=={{header|Octave}}==

 

=={{header|OpenEdge/Progress}}==

{{trans|Julia}}

define variable r as integer no-undo extent 3.

define variable m as integer no-undo initial 5.

 

combinations(1, 0).

{{out}}

0 1 2<br>

=={{header|Oz}}==

This can be implemented as a trivial application of finite set constraints:

fun {Comb M N}

proc {CombScript Comb}

end

in

 

=={{header|PARI/GP}}==

if( d == k,

print ( vecextract( v , "2..-2" ) )

}

 

 

if( z < b, print1( c, " " );

if( n>0, Cr( c+1, z , b* k \n, n-1, k - 1 ))

print

);

 

n--; k--;

while( k >= 0 ,

for( z = 0, bnk - 1,

Ci(z, b11, n, k ) );

 

=={{header|Pascal}}==

const

begin

generate(1);

 

{{out}}

The [https://metacpan.org/pod/ntheory ntheory] module has a combinations iterator that runs in lexicographic order.

{{libheader|ntheory}}

{{out}}

<pre>

[https://metacpan.org/pod/Algorithm::Combinatorics Algorithm::Combinatorics] also does lexicographic order and can return the whole array or an iterator:

{{libheader|Algorithm::Combinatorics}}

my @c = combinations( [0..4], 3 );

 

my $iter = combinations([0..4],3);

while (my $c = $iter->next) {

print "@$c\n";

 

[https://metacpan.org/pod/Math::Combinatorics Math::Combinatorics] is another option but results will not be in lexicographic order as specified by the task.

The major <i>Perl5i</i> -isms are the implicit "autoboxing" of the intermediate resulting array into an array object, with the use of unshift() as a method, and the "func" keyword and signature.

Note that Perl can construct ranges of numbers or of letters, so it is natural to identify the characters as 'a' .. 'e'.

use perl5i::2;

 

 

say @$_ for combine( 3, ('a'..'e') );

 

{{out}}

=={{header|Phix}}==

It does not get much simpler or easier than this. See [[Sudoku#Phix|Sudoku]] for a practical application of this algorithm

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">procedure</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>

<span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

{2,4,5}

{3,4,5}

</pre>

 

Much slower than normal algorithm.

 

<?php

 

 

?>

'''

Output:'''

===recursive===

 

 

function combinations_set($set = [], $size = 0) {

echo implode(", ", $combination), "\n";

}

 

Outputs:

=={{header|Picat}}==

===Recursion===

% Integers 1..K

N = 3,

comb1_(0, _X) = [[]].

comb1_(_M, []) = [].

 

{{out}}

 

===Using built-in power_set===

 

===Combinations from a list===

L = "abcde",

printf("comb3(%d,%w): %w\n",3,L,comb3(3,L)).

 

 

{{out}}

=={{header|PicoLisp}}==

{{trans|Scheme}}

(cond

((=0 M) '(NIL))

(comb M (cdr Lst)) ) ) ) )

 

 

=={{header|Pop11}}==

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

 

lvars ress = [];

define do_combs(l, m, el_lst);

enddefine;

 

 

=={{header|PowerShell}}==

An example of how PowerShell itself can translate C# code:

$source = @'

using System;

 

[Powershell.CSharp]::Combinations(3,5) | Format-Wide {$_} -Column 3 -Force

{{Out}}

<pre>

The solutions work with SWI-Prolog <BR>

Solution with library clpfd : we first create a list of M elements, we say that the members of the list are numbers between 1 and N and there are in ascending order, finally we ask for a solution.

 

comb_clpfd(L, M, N) :-

L ins 1..N,

chain(L, #<),

{{out}}

<pre> ?- comb_clpfd(L, 3, 5), writeln(L), fail.

false.</pre>

Another solution :

length(L, M),

fill(L, 1, N).

H1 is H + 1,

fill(T, H1, Max).

with the same output.

 

===List comprehension===

Works with SWI-Prolog, library '''clpfd''' from '''Markus Triska''', and list comprehension (see [[List comprehensions]] ).

comb_lstcomp(N, M, V) :-

V <- {L & length(L, N), L ins 1..M & all_distinct(L), chain(L, #<), label(L)}.

 

{{out}}

 

=={{header|Pure}}==

comb 0 _ = [[]];

comb _ [] = [];

end;

 

 

=={{header|PureBasic}}==

NewList comb.s()

; all possible combinations with {amount} Bits

EndProcedure

 

 

=={{header|Pyret}}==

 

fun combos<a>(lst :: List<a>, size :: Number) -> List<List<a>>:

 

 

 

=={{header|Python}}==

Starting from Python 2.6 and 3.0 you have a pre-defined function that returns an iterator. Here we turn the result into a list for easy printing:

>>> list(combinations(range(5),3))

 

Earlier versions could use functions like the following:

{{trans|E}}

if m == 0: return [[]]

return [[x] + suffix for i, x in enumerate(lst)

 

Example:

{{trans|Haskell}}

if m == 0: return [[]]

if s == []: return []

return [s[:1] + a for a in comb(m-1, s[1:])] + comb(m, s[1:])

 

 

A slightly different recursion version

def comb(m, s):

if m == 1: return [[x] for x in s]

return [s[:1] + a for a in comb(m-1, s[1:])] + comb(m, s[1:])

 

 

=={{header|Quackery}}==

===Bit Bashing===

 

[ dup 0 != while

dup 1 & if

3 5 comb

sortcombs

 

{{out}}

===Iterative===

 

[ stack ] is comb.items

[ stack ] is comb.required

 

3 5 comb

 

{{out}}

Can be used with <code>comb</code>, and is general purpose.

 

[ witheach

[ over swap peek swap ] ]

$ "zero one two three four" nest$

' [ 4 3 1 0 1 4 3 ] arrange

 

{{out}}

 

=={{header|R}}==

Combinations are organized per column,

so to provide an output similar to the one in the task text, we need the following:

 

=={{header|Racket}}==

{{trans|Haskell}}

 

(define sublists

(match-lambda**

(define (combinations n m)

(sublists n (range m)))

 

{{out}}

{{works with|rakudo|2015.12}}

There actually is a builtin:

{{out}}

<pre>(0 1 2)

 

Here is an iterative routine with the same output:

return ([],) unless $k;

return if $k > $n || $n <= 0;

}

}

 

=={{header|REXX}}==

This REXX program supports up to &nbsp; 100 &nbsp; symbols &nbsp; (one symbol for each "thing").

 

 

The symbol list could be extended by added any unique viewable symbol &nbsp; (character).

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; 3 &nbsp; 01234 </tt>}}

<pre>

0 1 2

0 1 3

1 3 4

2 3 4

</pre>

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; 3 &nbsp; abcde </tt>}}

<pre>

a b c

a b d

b d e

c d e

</pre>

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 44 &nbsp; 0 </tt>}}

<pre>

</pre>

<pre>

</pre>

 

=={{header|Ring}}==

# Project : Combinations

 

next

return aList

Output:

<pre>

[2 4 5]

[3 4 5]

</pre>

 

=={{header|Ruby}}==

{{works with|Ruby|1.8.7+}}

(0...n).to_a.combination(m).to_a

end

 

 

=={{header|Rust}}==

{{works with|Rust|0.9}}

fn comb<T: std::fmt::Default>(arr: &[T], n: uint) {

let mut incl_arr: ~[bool] = std::vec::from_elem(arr.len(), false);

comb(arr2, 3);

}

 

{{works with|Rust|1.26}}

struct Combo<T> {

data_len: usize,

}

}

 

{{works with|Rust|1.47|}}

fn comb<T>(slice: &[T], k: usize) -> Vec<Vec<T>>

where

return result;

}

 

=={{header|Scala}}==

def comb(n: Int) = recurse(m, List.range(0, n))

private def recurse(m: Int, l: List[Int]): List[List[Int]] = (m, l) match {

case _ => (recurse(m - 1, l.tail) map (l.head :: _)) ::: recurse(m, l.tail)

}

 

Usage:

 

Lazy version using iterators:

case _ if n < 0 || l.lengthCompare(n) < 0 => Iterator.empty

case 0 => Iterator(List.empty)

case x :: xs => combs(n - 1, xs).map(x :: _)

})

Usage:

<pre>

===Dynamic programming===

Adapted from Haskell version:

combsBySize(xs)(n)

 

 

def f[A](x: A, xsss: Stream[Stream[List[A]]]): Stream[Stream[List[A]]] =

Usage:

<pre>

===Using Scala Standard Runtime Library===

====Scala REPL====

====Other environments====

{{Out}}See it running in your browser by [https://scalafiddle.io/sf/DH34cqq/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/bwADub2XR8eu6bVVDbQw7g Scastie (JVM)].

=={{header|Scheme}}==

Like the Haskell code:

(cond ((= m 0) '(()))

((null? lst) '())

(comb m (cdr lst))))))

 

 

=={{header|Seed7}}==

 

const type: combinations is array array integer;

writeln;

end for;

 

{{out}}

 

=={{header|SETL}}==

 

=={{header|Sidef}}==

 

===Built-in===

 

===Recursive===

 

{{trans|Perl5i}}

 

set.len || return []

}

 

 

===Iterative===

 

if (k == 0) {

}

 

{{out}}

<pre>

{{works with|Pharo}}

{{works with|Squeak}}

(0 to: 4) combinations: 3 atATimeDo: [ :x | Transcript cr; show: x printString].

 

#(1 3 4)

#(2 3 4)"

 

=={{header|SPAD}}==

{{works with|OpenAxiom}}

{{works with|Axiom}}

[reverse subSet(5,3,i)$SGCF for i in 0..binomial(5,3)-1]

[1,3,4], [2,3,4]]

Type: List(List(Integer))

 

[http://fricas.github.io/api/SymmetricGroupCombinatoricFunctions.html?highlight=choose SGCF]

==> SymmetricGroupCombinatoricFunctions

 

=={{header|Standard ML}}==

| comb (_, [] ) = []

| comb (m, x::xs) = map (fn y => x :: y) (comb (m-1, xs)) @

comb (m, xs)

;

 

=={{header|Stata}}==

tempfile cp

tempvar k

}

sort `1'*

 

'''Example'''

 

. gen a=_n

. combin a 3

9. | 2 4 5 |

10. | 3 4 5 |

=== Mata ===

a = J(comb(n,k),k,.)

u = 1..k

}

 

 

'''Output'''

 

=={{header|Swift}}==

 

return (0..<pivotList.count)

}

 

{{out}}

<pre>[[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]]</pre>

=={{header|Tcl}}==

ref[http://wiki.tcl.tk/2553]

set set [list]

for {set i 0} {$i < $n} {incr i} {lappend set $i}

}

 

 

=={{header|TXR}}==

Combinations and permutations are produced in lexicographic order (except in the case of hashes).

 

(comb (range* 0 n) m))

 

 

{{out|Run}}

<pre>$ txr combinations.tl

3 comb 5 = ((0 1 2) (0 1 3) (0 1 4) (0 2 3) (0 2 4) (0 3 4) (1 2 4) (1 3 4) (2 3 4))</pre>

 

=={{header|Ursala}}==

Most of the work is done by the standard library function <code>choices</code>, whose implementation is shown here for the sake of comparison with other solutions,

where <code>leql</code> is the predicate that compares list lengths. The main body of the algorithm (<code>~&arh2fabt2RDfalrtPXPRT</code>) concatenates the results of two recursive calls, one of which finds all combinations of the required size from the tail of the list, and the other of which finds all combinations of one less size from the tail, and then inserts the head into each.

<code>choices</code> generates combinations of an arbitrary set but

not necessarily in sorted order, which can be done like this.

#import nat

 

* The sort combinator (<code>-<</code>) takes a binary predicate to a function that sorts a list in order of that predicate.

* The predicate in this case begins by zipping its two arguments together with <code>@p</code>.

* The overall effect of using everything starting from the <code>@p</code> as the predicate to a sort combinator is therefore to sort a list of lists of natural numbers according to the order of the numbers in the first position where they differ.

test program:

 

{{out}}

<pre><

=={{header|V}}==

like scheme (using variables)

[ [m zero?] [[[]]]

[lst null?] [[]]

[true] [m pred lst rest comb [lst first swap cons] map

m lst rest comb concat]

 

Using destructuring view and stack not *pure at all

[ [pop zero?] [pop pop [[]]]

[null?] [pop pop []]

[true] [ [m lst : [m pred lst rest comb [lst first swap cons] map

m lst rest comb concat]] view i ]

 

Pure concatenative version

[2dup [a b : a b a b] view].

[2pop pop pop].

[null?] [2pop []]

[true] [2dup [pred] dip uncons swapd comb [cons] map popd rollup rest comb concat]

 

Using it

 

=={{header|VBA}}==

Option Base 0

'Option Base 1

Transposition = T

Erase T

{{Out}}

If Option Base 0 :

3 4 5</pre>

{{trans|Phix}}

If needed = 0 Then '-- got a full set

For Each x In chosen: Debug.Print x;: Next x

Public Sub main()

comb 5, 3

 

=={{header|VBScript}}==

Function Dec2Bin(n)

q = n

'Testing with n = 5 / k = 3

Call Combination(5,3)

 

{{Out}}

=={{header|Wren}}==

{{libheader|Wren-perm}}

 

var fib = Fiber.new { Comb.generate((0..4).toList, 3) }

if (!c) return

System.print(c)

 

{{out}}

 

=={{header|XPL0}}==

def M=3, N=5;

int A(N-1);

];

 

 

{{out}}

=={{header|zkl}}==

{{trans|OCaml}}

seq=seq.makeReadOnly(); // because I append to parts of seq

fcn(k,seq){

.extend(self.fcn(k,seq[1,*]));

}(k,seq);

{{out}}<pre>L("abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde")</pre>