Реализации алгоритмов/Комбинаторика/Размещения: различия между версиями
Содержимое удалено Содержимое добавлено
DannyS712 (обсуждение | вклад) м <source> -> <syntaxhighlight> (phab:T237267) |
|||
Строка 1: | Строка 1: | ||
== Java == |
== Java == |
||
< |
<syntaxhighlight lang="java"> |
||
import java.util.Arrays; |
import java.util.Arrays; |
||
Строка 46: | Строка 46: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== Python == |
== Python == |
||
< |
<syntaxhighlight lang="python"> |
||
from numpy import zeros, int |
from numpy import zeros, int |
||
Строка 67: | Строка 67: | ||
p1 += 1 |
p1 += 1 |
||
return output |
return output |
||
</syntaxhighlight> |
|||
</source> |
|||
== Haskell == |
== Haskell == |
||
< |
<syntaxhighlight lang="ocaml"> |
||
import Control.Monad |
import Control.Monad |
||
permutationsWithRepetition xs = iterate (liftM2 (:) xs) [[]] |
permutationsWithRepetition xs = iterate (liftM2 (:) xs) [[]] |
||
Строка 79: | Строка 79: | ||
Prelude> permutationsWithRepetition [1,2,3] !! 2 |
Prelude> permutationsWithRepetition [1,2,3] !! 2 |
||
[[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]] |
||
</syntaxhighlight> |
|||
</source> |
|||
== C++ == |
== C++ == |
||
< |
<syntaxhighlight lang="C"> |
||
// pIn - входной массив |
// pIn - входной массив |
||
// N - размер входного массива |
// N - размер входного массива |
||
Строка 125: | Строка 125: | ||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== JavaScript == |
== JavaScript == |
||
< |
<syntaxhighlight lang="Javascript"> |
||
function PermutationsWithRepetition(src, len){ |
function PermutationsWithRepetition(src, len){ |
||
Строка 190: | Строка 190: | ||
perms.each(function(v){ console.log(v); }); // вывод всех размещений в консоль |
perms.each(function(v){ console.log(v); }); // вывод всех размещений в консоль |
||
</syntaxhighlight> |
|||
</source> |
|||
{{BookCat | filing = deep}} |
{{BookCat | filing = deep}} |
Версия от 16:00, 16 апреля 2020
Java
import java.util.Arrays;
public class PermutationsWithRepetition {
private Object[] source;
private int variationLength;
public PermutationsWithRepetition(Object[] source, int variationLength) {
this.source = source;
this.variationLength = variationLength;
}
public Object[][] getVariations() {
int srcLength = source.length;
int permutations = (int) Math.pow(srcLength, variationLength);
Object[][] table = new Object[permutations][variationLength];
for (int i = 0; i < variationLength; i++) {
int t2 = (int) Math.pow(srcLength, i);
for (int p1 = 0; p1 < permutations;) {
for (int al = 0; al < srcLength; al++) {
for (int p2 = 0; p2 < t2; p2++) {
table[p1][i] = source[al];
p1++;
}
}
}
}
return table;
}
public static void main(String[] args) {
PermutationsWithRepetition gen = new PermutationsWithRepetition(
new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0},
5);
Object[][] variations = gen.getVariations();
for (Object[] s : variations) {
System.out.println(Arrays.toString(s));
}
}
}
Python
from numpy import zeros, int
def permutations(n, length):
numbers = range(n)
permutations = n**length
output = zeros((permutations, length), dtype=int)
for i in range(length):
t2 = n**i
p1 = 0
while (p1 < permutations):
for al in range(n):
for p2 in range(t2):
output[p1, i] = numbers[al]
p1 += 1
return output
Haskell
import Control.Monad
permutationsWithRepetition xs = iterate (liftM2 (:) xs) [[]]
Prelude> take 4 (permutationsWithRepetition "ab")
[[""],["a","b"],["aa","ab","ba","bb"],["aaa","aab","aba","abb","baa","bab","bba","bbb"]]
Prelude> permutationsWithRepetition [1,2,3] !! 2
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
C++
// pIn - входной массив
// N - размер входного массива
// K - количество элементов в размещении
void PermutationWithRepetition(const char* pIn, int N, int K)
{
char* pOut = new char[K + 1]; // строка из K символов плюс 1 символ для терминального 0
pOut[K] = 0; // помещаем 0 в конец строки
K--;
int *stack = new int[K * 2], // стек псевдорекурсии, глубина рекурсии K - 1
*pTop = stack, // вершина стека
k = 0, // переменные цикла
n = 0,
j = 0;
for (;;) // цикл псевдорекурсии
{
while(n < N)
{
pOut[k] = pIn[n++];
if (k == K)
printf("%02d. %s\n", ++j, pOut);
else
{
if (n < N)
{
*pTop++ = k; // сохраняем k и n в стеке
*pTop++ = n;
}
k++; // псевдорекурсивный вызов
n = 0;
}
}
if (pTop == stack) // стек пуст, конец цикла
break;
n = *(--pTop); // выталкиваем k и n из стека
k = *(--pTop);
}
delete[] pOut;
delete[] stack;
}
JavaScript
function PermutationsWithRepetition(src, len){
var K = len - 1, k = 0,
N = src.length, n = 0,
out = [],
stack = [];
function next(){
while (true) {
while (n < src.length) {
out[k] = src[n++];
if (k == K) return out.slice(0);
else {
if (n < src.length) {
stack.push(k);
stack.push(n);
}
k++;
n = 0;
}
}
if (stack.length == 0) break;
n = stack.pop();
k = stack.pop();
}
return false;
}
function rewind(){ k = 0; n = 0; out = []; stack = []; }
function each(cb) {
rewind();
var v;
while (v = next()) if (cb(v) === false) return;
}
return {
next: next,
each: each,
rewind: rewind
};
}
/* пример использования */
var perms = PermutationsWithRepetition([1, 2, 3, 4, 5], 3);
perms.next(); // [1, 1, 1]
perms.next(); // [1, 1, 2]
//...
perms.next(); // [5, 5, 4]
perms.next(); // [5, 5, 5]
perms.next(); // false
perms.rewind();
perms.next(); // [1, 1, 1]
//...
perms.each(function(v){ console.log(v); }); // вывод всех размещений в консоль