Реализации алгоритмов/Комбинаторика/Размещения: различия между версиями
Содержимое удалено Содержимое добавлено
Maxal (обсуждение | вклад) Новая страница: «== Java == <source lang="java"> import java.util.Arrays; public class PermutationsWithRepetition { private Object[] source; private int variationLength; ...» |
JenVan (обсуждение | вклад) мНет описания правки |
||
Строка 126: | Строка 126: | ||
</source> |
</source> |
||
[[Категория:Программирование]] |
Версия от 18:03, 7 апреля 2011
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 array
def permutations(n,length):
numbers = range(n)
permutations = n**length
output = array([[0]*length]*permutations)
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;
}