Как сделать перестановку без повторов? - PullRequest
Новая
       25

Как сделать перестановку без повторов?

0 голосов
/ 04 июля 2019

Моя цель - проверить решение созданной мной игры. Как судоку, вы играете с сеткой. Сетка заставляет вас найти секретную комбинацию. Способ, которым я создаю сетку, делает невозможным убедиться, что существует только одно возможное решение, и если их несколько, сетка ложна. Поэтому я должен проверить сетку со всеми возможными комбинациями. Самый быстрый способ создать все комбинации - это сгенерировать все возможные присутствия каждого возможного числа комбинаций: например, [1,1,1 | 1,2,0 | 3,0,0], если длина комбинации составляет 3 и три возможных значения. С этой информацией мне нужно использовать перестановку.

Вот сценарий, который я написал: 

function recursion($grd_chfr, $pt_chfr, $tab, &$tab_all) {
    if($grd_chfr == 0) {
        $tab_all[] = $tab;
        return;
    }
    for($n = $pt_chfr; $n <= $grd_chfr; $n++) {
        $b = $tab;
        $b[] =  $n;
        recursion($grd_chfr - $n, $n, $b, $tab_all);
    }
}

function permutations(array $elements)
{
    if (count($elements) <= 1) {
        yield $elements;
    } else {
        foreach (permutations(array_slice($elements, 1)) as $permutation) {
            foreach (range(0, count($elements) - 1) as $i) {
                yield array_merge(
                    array_slice($permutation, 0, $i),
                    [$elements[0]],
                    array_slice($permutation, $i)
                );
            }
        }
    }
}

$somme = 7;
$depart = 1;
$entrees = 7;
$tab_all = [];

$time_start = microtime(true);

// I use a recursive function to get every manner to spread values, to fill the combination whose length is $somme
recursion($somme, $depart, [], $tab_all);

$new_tab_all = [];
$count_gen = 0;

//  if the number of possible values to use ($entrees) is higher or smaller than the length of the combination I adjust by adding zeros or by deleting distributions
foreach($tab_all as $tab){
    if(count($tab) < $entrees){
        $count = count($tab);
        for($x = $depart; $x <= $entrees - $count; $x++){
            $tab[] = 0;
        }
        //  I create all possible permutation for each distribution, and that's where there is too much duplicatas
        foreach(permutations($tab) as $combi){
            if(!in_array($combi, $new_tab_all)) {
                $new_tab_all[] = $combi;
            }
        }
    }
    elseif(count($tab) == $entrees){
        $new_tab_all[] = $tab;
    }
}


$time_stop = microtime(true);
echo round(($time_stop - $time_start), 2)."s d'écoulées, ".count($new_tab_all)." solutions (".$count_gen." générées).</br></br>";

Мне нужен скрипт, чтобы получить все возможные уникальные перестановки комбинации. Например, имея массив [1,1,2,3], мне нужен скрипт, возвращающий [[1,1,3,2], [1,3,1,2], [3,1,1, 2], [2,1,3,1], [2,3,1,1], [1,3,2,1], [1,1,2,3], ...] никогда не имеющие дважды одна и та же комбинация.

Для создания перестановок я использую скрипт, но он генерирует много повторений с такими комбинациями, как [1,1,1,1,2,3]. Я нашел это там: Перестановки - все возможные наборы чисел 

function permutations(array $elements)
{
    if (count($elements) <= 1) {
        yield $elements;
    } else {
        foreach (permutations(array_slice($elements, 1)) as $permutation) {
            foreach (range(0, count($elements) - 1) as $i) {
                yield array_merge(
                    array_slice($permutation, 0, $i),
                    [$elements[0]],
                    array_slice($permutation, $i)
                );
            }
        }
    }
}

Я также нашел скрипт, который, как мне кажется, мне нужен, но он написан на python, и он мне нужен в php. Я нашел это там: перестановок с уникальными значениями 

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1




a = list(perm_unique([1,1,2]))
print(a)

Я не знаю, как перевести второй код в php или как изменить первый код, чтобы исключить повторы.

1 Ответ

0 голосов
/ 04 июля 2019
  • Вы начинаете с оригинальной коллекции, скажем, [a, b, a]
  • теперь нужно разобрать коллекцию
  • для каждого уникального элемента коллекции вы создаете список, начинающийся с текущего элемента и сопровождаемый перестановкой коллекции за вычетом текущего элемента (повторение здесь разрешено) как это: псевдокод рекурсивного алгоритма перестановки
...