Permutations with repetitions: Difference between revisions

{{draft task|Probability and statistics}}

'''Generate''' a sequence of permutations of n elements drawn from choice of k values.

 

 

Do not store all the intermediate values of the sequence, rather generate them as required, and pass the intermediate result to a deciding routine for combinations selection and/or early generator termination.

'''See Also:'''

{{Template:Combinations and permutations}}

 

=={{header|ALGOL 68}}==

{{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''.}}

 

MODE PERMELEMLIST = FLEX[0]PERMELEM;

);

 

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

 

# OD #));

done: SKIP

<pre>

Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa;

Nicole Kidman; Keith Urban; Chris Ciaffa; Chris Ciaffa; => Sunday + Faith as extras

</pre>

 

=={{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|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|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:

aba

bba</pre>

 

=={{header|jq}}==

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

 

 

{{out}}

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

 

=={{header|Perl}}==

{{out}}

<pre>[A A] [A B] [A C] [B A] [B B] [B C] [C A] [C B] [C C]</pre>

 

Solving the crack problem:

my $iter = tuples_with_repetition([qw/A C K R/], 5);

my $tries = 0;

$tries++;

die "Found the combination after $tries tries!\n" if join("",@$p) eq "CRACK";

{{out}}

<pre>Found the combination after 455 tries!</pre>

 

{{out}}

 

 

{{out}}

 

=={{header|PicoLisp}}==

(if (=0 N)

(cons NIL)

'((X)

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

 

=={{header|Python}}==

 

# check permutations until we find the word 'crack'

w = ''.join(x)

print w

 

=={{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

 

 

11

12

33

</pre>

bat,bat

bat,fox

<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===

say j

<pre>

11

32

33

</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>

List(List(1, 1), List(1, 2), List(1, 3), List(2, 1), List(2, 2), List(2, 3), List(3, 1), List(3, 2), List(3, 3))

</pre>

 

=={{header|Tcl}}==

===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