Permutations with repetitions: Difference between revisions

{{Template:Combinations and permutations}}

<br>

 

=={{header|AppleScript}}==

Permutations with repetitions, using strict evaluation, generating the entire set (where system constraints permit) with some degree of efficiency. For lazy or interruptible evaluation, see the second example below.

 

 

 

 

on run

end run

 

 

 

script

on |λ|(x)

script

on |λ|(y)

end |λ|

end script

concatMap(result, ys)

end |λ|

end script

concatMap(result, xs)

 

-- Lift 2nd class handler function into 1st class script wrapper

on mReturn(f)

if class of f is script then

end script

end if

{{Out}}

 

Permutations with repetition by treating the <math>n^k</math> elements as an ordered set, and writing a function from a zero-based index to the nth permutation. This allows us terminate a repeated generation on some condition, or explore a sub-set without needing to generate the whole set:

 

-- nthPermutationWithRepn :: [a] -> Int -> Int -> [a]

set intBase to length of xs

end if

end nthPermutationWithRepn

 

end |λ|

end script

 

 

on run

end run

 

 

 

else

end if

end repeat

 

 

-- Lift 2nd class handler function into 1st class script wrapper

on mReturn(f)

if class of f is script then

end mReturn

 

-- replicate :: Int -> a -> [a]

on replicate(n, a)

end replicate

 

-- unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

on unfoldr(f, v)

tell mReturn(f)

end repeat

end tell

{{Out}}

 

 

 

 

 

 

 

=={{header|AutoHotkey}}==

Use the function from http://rosettacode.org/wiki/Permutations#Alternate_Version with opt=1

;1..n = range, or delimited list, or string to parse

; to process with a different min index, pass a delimited list, e.g. "0`n1`n2"

. P(n,k-1,opt,delim,str . A_LoopField . delim)

Return s

 

=={{header|C}}==

#include <stdlib.h>

 

int temp;

int numbers=3;

for( temp2 = 1 ; temp2 <= numbers; temp2++){

a[temp2]=1;

}

a[numbers]=0;

while(1){

if(a[temp]==upto){

}

return 0;

{{out}}

<pre>(111)(112)(113)(114)(121)(122)(123)(124)(131)(132)(133)(134)(141)(142)(143)(144)(211)(212)(213)(214)(221)(222)(223)(224)(231)(232)(233)(234)(241)(242)(243)(244)(311)(312)(313)(314)(321)(322)(323)(324)(331)(332)(333)(334)(341)(342)(343)(344)(411)(412)(413)(414)(421)(422)(423)(424)(431)(432)(433)(434)(441)(442)(443)(444)</pre>

 

=={{header|D}}==

===opApply Version===

{{trans|Scala}}

 

struct PermutationsWithRepetitions(T) {

import std.stdio, std.array;

[1, 2, 3].permutationsWithRepetitions(2).array.writeln;

{{out}}

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

===Generator Range Version===

{{trans|Scala}}

 

Generator!(T[]) permutationsWithRepetitions(T)(T[] data, in uint n)

void main() {

[1, 2, 3].permutationsWithRepetitions(2).writeln;

The output is the same.

 

=={{header|EchoLisp}}==

(lib 'sequences) ;; (indices ..)

(lib 'list) ;; (list-permute ..)

(list-permute '(a b c d e) #(1 0 1 0 3 2 1))

→ (b a b a d c b)

 

=={{header|Elixir}}==

{{trans|Erlang}}

def perm_rep(list), do: perm_rep(list, length(list))

Enum.each(1..3, fn n ->

IO.inspect RC.perm_rep(list,n)

 

{{out}}

 

=={{header|Erlang}}==

-export([permute/1]).

 

permute([],_) -> [[]];

permute(_,0) -> [[]];

 

=={{header|Go}}==

 

import "fmt"

}

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

{{out}}

<pre>

Position in the sequence is an integer from <code>i.n^k</code>, for example:

 

 

The sequence itself is expressed using <code>(k#n)#: position</code>, for example:

 

0 0

0 1

2 0

2 1

 

Partial sequences belong in a context where they are relevant and the sheer number of such possibilities make it inadvisable to generalize outside of those contexts. But anything that can generate integers will do. For example:

 

1 0

1 1

 

We might express this as a verb

 

 

with example use:

 

0 0

0 1

0 2

1 0

 

but the structural requirements of this task (passing intermediate results "when needed") mean that we are not looking for a word that does it all, but are instead looking for components that we can assemble in other contexts. This means that the language primitives are what's needed here.

=={{header|Java}}==

{{works with|Java|8}}

 

public class PermutationsWithRepetitions {

}

}

 

Output:

Permutations with repetitions, using strict evaluation, generating the entire set (where system constraints permit) with some degree of efficiency. For lazy or interruptible evaluation, see the second example below.

 

'use strict';

 

 

//--> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

 

{{Out}}

 

Permutations with repetition by treating the <math>n^k</math> elements as an ordered set, and writing a function from a zero-based index to the nth permutation. This allows us terminate a repeated generation on some condition, or explore a sub-set without needing to generate the whole set:

 

'use strict';

 

return show(range(30, 35)

.map(curry(nthPermutationWithRepn)(['X', 'Y', 'Z'], 4)));

 

{{Out}}

A (strict) analogue of the (lazy) replicateM in Haskell.

 

'use strict';

 

);

// -> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

{{Out}}

 

 

Permutations with repetition by treating the <math>n^k</math> elements as an ordered set, and writing a function from a zero-based index to the nth permutation. Wrapping this function in a generator allows us terminate a repeated generation on some condition, or explore a sub-set without needing to generate the whole set:

 

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>Generated 589 of 1024 possible permutations,

We shall define permutations_with_replacements(n) in terms of a more general filter, combinations/0, defined as follows:

 

# Output: a stream of arrays, c, with c[i] drawn from $in[i].

def combinations:

# Output: a stream of arrays of length n with elements drawn from the input array.

def permutations_with_replacements(n):

'''Example 1: Enumeration''':

 

Count the number of 4-combinations of [0,1,2] by enumerating them, i.e., without creating a data structure to store them all.

 

count([0,1,2] | permutations_with_replacements(4))

 

 

Counting from 1, and terminating the generator when the item is found, what is the sequence number of ["c", "a", "b"] in the stream

of 3-combinations of ["a","b","c"]?

# Output: the index of the item in the stream (counting from 1);

# emit null if the item is not found

["c", "a", "b"] | sequence_number( ["a","b","c"] | permutations_with_replacements(3))

 

 

=={{header|Julia}}==

Implements a simil-Combinatorics.jl API.

 

a::T

t::Int

 

println("Permutations of [4, 5, 6] in 3:")

 

{{out}}

[5, 6, 6]

[6, 6, 6]</pre>

=={{header|K}}==

enlist each from x on the left and each from x on the right where x is range 10

,/x/:\:x:!10

 

=={{header|Kotlin}}==

{{trans|Go}}

 

fun main(args: Array<String>) {

}

}

 

{{out}}

 

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

Module Checkit {

a=("A","B","C","D")

}

Checkit

{{out}}

<pre style="height:30ex;overflow:scroll">

</pre >

 

{{out}}

<pre>{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}</pre>

 

{{out}}

 

 

 

 

 

 

 

 

 

{{out}}

 

=={{header|Pascal}}==

{{works with|Free Pascal}}

Create a list of indices into what ever you want, one by one.

Doing it by addig one to a number with k-positions to base n.

//permutations with repetitions

//http://rosettacode.org/wiki/Permutations_with_repetitions

until Not(NextPermWithRep(p));

writeln('k: ',k,' n: ',n,' count ',cnt);

{{Out}}

<pre>

//"old" compiler-version

//real 0m3.465s /fpc/2.6.4/ppc386 "%f" -al -Xs -XX -O3</pre>

 

=={{header|PHP}}==

function permutate($values, $size, $offset) {

$count = count($values);

echo join(',', $permutation)."\n";

}

 

{{out}}

 

=={{header|PicoLisp}}==

(if (=0 N)

(cons NIL)

'((X)

(mapcar '((Y) (cons Y X)) Lst) )

 

=={{header|Python}}==

 

To evaluate the whole set of permutations, without the option to make complete evaluation conditional, we can reach for a generic replicateM function for lists:

 

 

 

# main :: IO ()

def main():

print(

)

 

 

# GENERIC FUNCTIONS ---------------------------------------

 

# liftA2List :: (a -> b -> c) -> [a] -> [b] -> [c]

def liftA2List(f):

 

 

)

 

 

# MAIN ---

{{Out}}

 

===Lazy evaluation with a generator===

====Applying itertools.product====

 

 

# check permutations until we find the word 'crack'

w = ''.join(x)

print w

 

====Writing a generator====

 

Or, composing our own generator, by wrapping a function '''from''' an index in the range ''0 .. ((distinct items to the power of groupSize) - 1)'' '''to''' a unique permutation. (Each permutation is equivalent to a 'number' in the base of the size of the set of distinct items, in which each distinct item functions as a 'digit'):

 

 

 

def groupsOfSize(n):

f = nthPermWithRepn(xs)(n)

limit = len(xs)**n

i = 0

yield f(i)

i = 1 + i

# nthPermWithRepn :: [a] -> Int -> Int -> [a]

def nthPermWithRepn(xs):

def go(intGroup, index):

vs = list(xs)

intSet = intBase ** intGroup

return (

)(index): (

list(repeat(vs[0], intGroup - len(ds))) + ds

 

 

 

 

# Just :: a -> Maybe a

def Just(x):

 

 

# Nothing :: Maybe a

def Nothing():

 

 

# concat :: [[a]] -> [a]

def concat(xs):

return (

)

 

 

 

 

# unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

def unfoldr(f):

def go(v):

xs = []

while True:

if mb.get('Nothing'):

return xs

else:

xr = mb.get('Just')

return xs

 

 

{{Out}}

 

=={{header|Racket}}==

===As a sequence===

First we define a procedure that defines the sequence of the permutations.

(define (permutations-with-repetitions/proc size items)

(define items-vector (list->vector items))

continue-after-pos+val?))))

{{out}}

<pre>'((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))</pre>

===As a sequence with for clause support===

Now we define a more general version that can be used efficiently in as a for clause. In other uses it falls back to the sequence implementation.

(define-sequence-syntax in-permutations-with-repetitions

(for/list ([element (in-permutations-with-repetitions 2 '(1 2 3))])

element)

{{out}}

<pre>'((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

'((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))</pre>

 

=={{header|REXX}}==

===version 1===

parse arg things bunch inbetweenChars names

/* ╔════════════════════════════════════════════════════════════════╗ */

@.?= $.q; call .permSet ?+1

end /*q*/

{{out|output|text=&nbsp; when using the default inputs of: &nbsp; &nbsp; <tt> 3 &nbsp; 2 </tt>}}

<pre>

<br>&nbsp;&nbsp;Say 'too large for this Rexx version'

<br>Also note that the output isn't the same as REXX version 1 when the 1st argument is two digits or more, i.e.: &nbsp; '''11 &nbsp; 2'''

* Arguments and output as in REXX version 1 (for the samples shown there)

* For other elements (such as 11 2), please specify a separator

a=a||'Say' p 'permutations'

/* Say a */

 

===version 3===

 

This version could easily be extended to '''N''' up to 15 &nbsp; (using hexadecimal arithmetic).

parse arg N M .

z= N**M

t= t+1

say j

{{out|output|text= &nbsp; when using the following inputs: &nbsp; &nbsp; <tt> 3 &nbsp; 2 </tt>}}

<pre>

 

=={{header|Ring}}==

# Project : Permutations with repetitions

next

see nl

Output:

<pre>

=={{header|Ruby}}==

This is built in　(Array#repeated_permutation):

p rp.to_a #=>[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

 

#yield permutations until their sum happens to exceed 4, then quit:

 

=={{header|Scala}}==

 

object PermutationsRepTest extends Application {

}

println(permutationsWithRepetitions(List(1, 2, 3), 2))

{{out}}

<pre>

 

=={{header|Sidef}}==

var n = 2

 

{{out}}

<pre>

c c

</pre>

 

=={{header|Tcl}}==

===Iterative version===

{{trans|PHP}}

proc permutate {values size offset} {

set count [llength $values]

# Usage

permutations [list 1 2 3 4] 3

 

===Version without additional libraries===

{{works with|Tcl|8.6}}

{{trans|Scala}}

 

# Utility function to make procedures that define generators

# Demonstrate usage

set g [permutationsWithRepetitions {1 2 3} 2]

===Alternate version with extra library package===

{{tcllib|generator}}

{{works with|Tcl|8.6}}

package require generator

 

generator foreach val [permutationsWithRepetitions {1 2 3} 2] {

puts $val