Генерация упорядоченных (взвешенных) комбинаций произвольной длины в PHP - PullRequest
Новая
       22

Генерация упорядоченных (взвешенных) комбинаций произвольной длины в PHP

4 голосов
/ 21 июня 2009

С учетом списка распространенных слов, отсортированных по степени распространенности использования, можно сформировать словосочетания произвольной длины (любое желаемое количество слов) в порядке «наиболее распространенных» последовательностей. Например, если наиболее распространенными словами являются «a, b, c», то для комбинаций длины два будет сгенерировано следующее: 

aa
ab
ba
bb
ac
bc
ca
cb
cc

Вот правильный список для длины 3: 

aaa
aab
aba
abb
baa
bab
bba
bbb
aac
abc
bac
bbc
aca
acb
bca
bcb
acc
bcc
caa
cab
cba
cbb
cac
cbc
cca
ccb
ccc

Это просто реализовать для комбинаций из 2 или 3 слов (заданной длины) для любого количества элементов, но можно ли это сделать для произвольной длины? Я хочу реализовать это в PHP, но псевдокод или даже краткое изложение алгоритма будет высоко ценится!

Ответы [ 4 ]

1 голос
/ 22 июня 2009

Вот рекурсивная функция, которая может быть тем, что вам нужно. Идея состоит в том, чтобы при наличии длины и буквы сначала генерировать все последовательности, которые на одну букву короче и не содержат этой буквы. Добавьте новое письмо в конец, и вы получите первую часть последовательности, которая включает в себя эту букву. Затем переместите новую букву влево. Просмотрите каждую последовательность букв , включая новую справа.

Так что, если у вас был gen (5, d) Это началось бы с 

(aaaa)d
(aaab)d
...
(cccc)d

тогда, когда это было сделано с комбинациями a-c, это сделало бы 

(aaa)d(a)
...
(aaa)d(d)
(aab)d(d)
... 
(ccc)d(d)

тогда, когда это было сделано с d как 4-ой буквой, это переместило бы это к 3-ьему 

(aa)d(aa)

и т. Д. И т. П. 

<?php 
/** 
 * Word Combinations (version c) 6/22/2009 1:20:14 PM 
 * 
 * Based on pseudocode in answer provided by Erika: 
 *   /1056570/generatsiya-uporyadochennyh-vzveshennyh-kombinatsii-proizvolnoi-dliny-v-php 
 *   (direct link to Erika's answer) 
 * 
 * To see the results of this script, run it: 
 *   http://stage.dustinfineout.com/stackoverflow/20090622/word_combinations_c.php 
**/ 

init_generator(); 

function init_generator() { 
    global $words; 
    $words = array('a','b','c'); 
    generate_all(5);


} 

function generate_all($len){
    global $words;
    for($i = 0; $i < count($words); $i++){
        $res = generate($len, $i); 

        echo join("<br />", $res);  
        echo("<br/>");
    }   
}

function generate($len, $max_index = -1){ 
    global $words; 

    // WHEN max_index IS NEGATIVE, STARTING POSITION 
    if ($max_index < 0) { 
        $max_index = count($words) - 1; 
    } 

    $list = array(); 


    if ($len <= 0) { 
        $list[] = "";
        return $list; 
    } 

    if ($len == 1) { 

        if ($max_index >= 1) { 
            $add = generate(1, ($max_index - 1));
            foreach ($add as $addit) { 
                $list[] = $addit; 
            } 


        } 
        $list[] = $words[$max_index]; 
        return $list; 
    } 

    if($max_index == 0) { 
        $list[] = str_repeat($words[$max_index], $len); 
        return $list; 
    } 

    for ($i = 1; $i <= $len; $i++){ 
        $prefixes = generate(($len - $i), ($max_index - 1)); 
        $postfixes = generate(($i - 1), $max_index); 
        foreach ($prefixes as $pre){ 
            //print "prefix = $pre<br/>";
            foreach ($postfixes as $post){ 
                //print "postfix = $post<br/>";
                $list[] = ($pre . $words[$max_index] . $post); 
            } 
        } 
    } 
    return $list; 
} 

?>
0 голосов
/ 21 июня 2009

Я не знаю, что означает термин для того, что вы пытаетесь вычислить, но это не комбинации или даже перестановки, это своего рода перестановки с повторением.

Ниже я приложил немного адаптированный код из ближайшей вещи, которая у меня есть, которая делает что-то вроде этого, генератор перестановок строк в LPC. Для a, b, c он генерирует 

abc
bac
bca
acb
cab
cba

Вероятно, его можно настроить, чтобы включить поведение повторения, которое вы хотите. 

varargs mixed array permutations(mixed array list, int num) {
    mixed array out = ({});
    foreach(mixed item : permutations(list[1..], num - 1))
        for(int i = 0, int j = sizeof(item); i <= j; i++)
            out += ({ implode(item[0 .. i - 1] + ({ list[0] }) + item[i..], "") });
    if(num < sizeof(list))
        out += permutations(list[1..], num);
    return out;
}

FWIW, другой способ сформулировать вашу проблему состоит в том, что для ввода из N элементов вы хотите установить набор всех путей длины N в полностью связном, самосвязанном графе с элементами ввода в качестве узлов. *

0 голосов
/ 21 июня 2009

Я предполагаю, что, говоря, что это легко для фиксированной длины, вы используете m вложенных циклов, где m - длина последовательности примеры).

Вы можете использовать рекурсию следующим образом:

Ваши слова пронумерованы 0, 1, .. n, вам нужно сгенерировать все последовательности длиной m : 

generate all sequences of length m:
{
    start with 0, and generate all sequences of length m-1
    start with 1, and generate all sequences of length m-1
    ...
    start with n, and generate all sequences of length m-1 
}

generate all sequences of length 0
{
    // nothing to do
}

Как это реализовать? Что ж, при каждом вызове вы можете поместить еще один элемент в конец массива, а когда вы достигнете конца рекурсии, выведите содержимое массива: 

// m is remaining length of sequence, elements is array with numbers so far
generate(m, elements)
{
    if (m == 0)
    {
        for j = 0 to elements.length print(words[j]);
    }
    else
    {
        for i = 0 to n - 1
        {
            generate(m-1, elements.push(i));
        }   
    }
}

И, наконец, назовите это так: generate (6, array ())

0 голосов
/ 21 июня 2009

Я гуглил по php-перестановкам и получил: http://www.php.happycodings.com/Algorithms/code21.html

Я не изучал код, хорош он или нет. Но, похоже, делает то, что ты хочешь.

...