Permutations with repetitions: Difference between revisions

{{trans|Kotlin}}

 

V values = [‘A’, ‘B’, ‘C’, ‘D’]

V k = values.len

i++

I i == n

 

{{out}}

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

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.

 

-- {{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {2, 1, 1},

-- {2, 1, 2}, {2, 2, 1}, {2, 2, 2}}

end script

end if

{{Out}}

 

===Lazy evaluation with a generator===

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 framework "Foundation"

use scripting additions

end tell

return xs

{{Out}}

<pre>Permutation 589 of 1024: CRACK

Found after searching from AAAAA thru ARACK</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|AWK}}==

# syntax: GAWK -f PERMUTATIONS_WITH_REPETITIONS.AWK

# converted from C

exit(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|C}}==

#include <stdlib.h>

 

}

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|C++}}==

#include <stdio.h>

#include <stdlib.h>

}

 

{{out}}

<pre>

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

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

 

=={{header|Maxima}}==

{{out}}

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

 

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

 

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

Asking for the 0th permutation just returns the total number of permutations (ie "").<br>

Results can be generated in any order, hence early termination is quite simply a non-issue.

{{out}}

<pre>

reverse(permrep("ACKR",5,589+1):CRACK

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

{{Works with|Python|3.7}}

 

from itertools import product

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Permutations of two elements, drawn from three values:

====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'):

{{Works with|Python|3.7}}

 

from itertools import (chain, repeat)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Search for a 5 char permutation drawn from 'ACKR' matching "crack":

 

Permutation 589 of 1024: CRACK</pre>

 

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

 

{{works with|rakudo|2016.07}}

 

 

For arbitrary <math>n</math>:

 

{{works with|rakudo|2016.07}}

my $n = 2;

 

 

{{out}}

 

{{works with|rakudo|2016.07}}

my $n = 2;

 

 

{{out}}

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

struct PermutationIterator<'a, T: 'a> {

universe: &'a [T],

}

 

{{out}}

<pre>

 

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

 

=={{header|Wren}}==

{{trans|Kotlin}}

var values = ["A", "B", "C", "D"]

var k = values.count

if (i == n) return // all permutations generated

}

 

{{out}}

<pre>