함수 permutations list()

1 PHP

<?php
# http://pyrus.syntaxhighlightforge.net/Math_Combinatorics.html
class Permutations {
    private static $_pointers = [];
    public static function get(array $set, $subset_size = null) {
        $combinations = self::combinations($set, $subset_size);
        $permutations = [];
        foreach ($combinations as $combination) {
            $permutations = array_merge($permutations, self::_findPermutations($combination));
        }
        return $permutations;
    }
    private static function _findPermutations($set) {
        if (count($set) <= 1) return array($set);
        $permutations = [];
        list($key, $val) = self::array_shift_assoc($set);
        $sub_permutations = self::_findPermutations($set);
        foreach ($sub_permutations as $permutation) {
            $permutations[] = array_merge(array($key => $val), $permutation);
        }
        $set[$key] = $val;
        $start_key = $key;
        $key = array_keys($set)[0];
        while ($key != $start_key) {
            list($key, $val) = self::array_shift_assoc($set);
            $sub_permutations = self::_findPermutations($set);
            foreach ($sub_permutations as $permutation) {
                $permutations[] = array_merge(array($key => $val), $permutation);
            }
            $set[$key] = $val;
            $key = array_keys($set)[0];
        }
        return $permutations;
    }
    public static function array_shift_assoc(array &$array) {
        foreach ($array as $key => $val) {
            unset($array[$key]);
            break;
        }
        return array($key, $val);
    }
    private static function combinations(array $set, $subset_size=null) {
        $set_size = count($set);
        if (is_null($subset_size)) $subset_size = $set_size;
        if ($subset_size >= $set_size) return array($set);
        if ($subset_size == 1) return array_chunk($set, 1);
        if ($subset_size == 0) return array();
        $combinations = [];
        $set_keys = array_keys($set);
        self::$_pointers = array_slice(array_keys($set_keys), 0, $subset_size);
        $combinations[] = self::_getCombination($set);
        while (self::_advancePointers($subset_size - 1, $set_size - 1)) {
            $combinations[] = self::_getCombination($set);
        }
        return $combinations;
    }
    private static function _getCombination($set) {
        $set_keys = array_keys($set);
        $combination = [];
        foreach (self::$_pointers as $pointer) $combination[$set_keys[$pointer]] = $set[$set_keys[$pointer]];
        return $combination;
    }
    private static function _advancePointers($pointer_number, $limit) {
        if ($pointer_number < 0) return false;
        if (self::$_pointers[$pointer_number] < $limit) {
            self::$_pointers[$pointer_number]++;
            return true;
        }
        if (self::_advancePointers($pointer_number - 1, $limit - 1)) {
            self::$_pointers[$pointer_number] = self::$_pointers[$pointer_number - 1] + 1;
            return true;
        }
        return false;
    }
}
$rows = Permutations::get([1,2,3],2);
foreach($rows as $row) echo implode(',', $row) . PHP_EOL;
# 1,2
# 2,1
# 1,3
# 3,1
# 2,3
# 3,2

2 Python

import itertools
lst = list(itertools.permutations([1,2,3],2))
print( lst )
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

3 같이 보기

• 순열
• 함수 combinations_list()