Хорошо, ребята, мне нужно реализовать это для фотоконкурса … у меня есть основной набор N изображений, и мне нужно сгенерировать перестановки размером 2 этих фото без повторений, например:
foo.png VS bar.png
равно
bar.png VS foo.png
Другое дело, я не могу предварительно генерировать al-перестановки каждый раз, поэтому мне нужна функция, которая, учитывая предыдущую перестановку, вернет мне следующую (или NULL, если возможные уникальные перестановки завершены).
Я решил эту проблему со следующей функцией PHP:
function getNextPermutation( $aPermutableItems, $iPermutationSize, $aPreviousPermutation = NULL ) { $aNextPermutation = $aPreviousPermutation; $iLastIndex = $iPermutationSize - 1; $iPermutableItems = count($aPermutableItems); // Any previous permutation ? if( $aPreviousPermutation ) { // Loop the elements backwards for( $i = $iLastIndex; $i >= 0; $i-- ) { // Can the current element be incremented without reaching the limit ? if( ++$aNextPermutation[ $i ] >= $iPermutableItems ) { // Increment the previous element $iPrevValue = ++$aNextPermutation[ $i - 1 ]; // Reset the current element with the value of the previous plus one $iNextValue = $aNextPermutation[ $i ] = $iPrevValue + 1; // Skip the previous element because it was just incremented $i--; // If one of the two elements reached the limit, we are in the exit condition if( $iPrevValue >= $iPermutableItems || $iNextValue >= $iPermutableItems ) return FALSE; } // Limit still to be reached for the i-th element, skip previous ones else break; } } // Am i able to generate the first permutation ? else if( $iPermutationSize <= $iPermutableItems ) $aNextPermutation = range( 0, $iLastIndex ); // Permutation impossible to generate because we don't have enough elements in the main set else $aNextPermutation = FALSE; return $aNextPermutation; } Так что:
$iPerm = 0; $aPrev = NULL; $aItems = array( 0, 1, 2, 3, 4 ); while( ($aPrev = getNextPermutation( $aItems, 2, $aPrev )) != FALSE ) { echo sprintf( "%2d : %s\n", $iPerm++, implode( ', ', $aPrev ) ); }
Вывод:
0 : 0, 1 1 : 0, 2 2 : 0, 3 3 : 0, 4 4 : 1, 2 5 : 1, 3 6 : 1, 4 7 : 2, 3 8 : 2, 4 9 : 3, 4
Теперь я действительно хотел бы добавить к ней некоторую энтропию … что я имею в виду, так как вы видите, первый элемент в комбинациях часто повторяется (0,1 0,2 0,3), и в моем случае это не хорошо, потому что я увижу ту же картину для 4 постоянных перестановок.
Есть ли способ изменить (или повторить) мой алгоритм, чтобы иметь что-то вроде (например):
0 : 0, 1 1 : 1, 2 2 : 0, 3 3 : 3, 4 4 : 0, 2 5 : 1, 3 6 : 0, 4 7 : 2, 3 8 : 2, 4 9 : 1, 4
Очевидно, я не могу просто перетасовать массив перестановок, потому что, как я писал, у меня нет всего массива перестановок, но только предыдущая перестановка, которая даст мне следующий, как только будет применен мой алгоритм.
PS: У меня есть около 500 фотографий для каждой задачи, поэтому хранить битмаски или подобные вещи неприемлемы.
Благодарю.