Реализации алгоритмов/Комбинаторика/Размещения: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Новая страница: «== Java == <source lang="java"> import java.util.Arrays; public class PermutationsWithRepetition { private Object[] source; private int variationLength; ...»
 
мНет описания правки
Строка 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;
}