За последние 24 часа нас посетили 16568 программистов и 1644 робота. Сейчас ищут 1677 программистов ...

Как реализовать перестановку на РНР?

Тема в разделе "Прочие вопросы по PHP", создана пользователем bambet, 30 окт 2009.

  1. bambet

    bambet Активный пользователь

    С нами с:
    6 окт 2009
    Сообщения:
    4
    Симпатии:
    0
    Здравствуйте. Помогите пожалуйста советом. Нужно реализовать перестановку (в Комбинаторике это называется "размещение с повторением") на РНР.
    Для примера, есть массив чисел 1,2,3. Нужно вычислить все варианты:
    123
    132
    312... и т.д.

    Спасибо.
     
  2. iliavlad

    iliavlad Активный пользователь

    С нами с:
    24 янв 2009
    Сообщения:
    1.689
    Симпатии:
    4
    для этого нужно написать алгоритм, а потом, используя конструкции языка, реализовать его.

    ПС. чисто функции в пхп
    array getRazmeschenieSPovtoreniem(array $source)
    наверное нету.
     
  3. sylex

    sylex Активный пользователь

    С нами с:
    9 ноя 2008
    Сообщения:
    625
    Симпатии:
    0
    Адрес:
    Омск
    помню как-то реализовывал такое... не слишком то и сложно :)

    Могу сделать платно ;)
     
  4. karakh

    karakh Активный пользователь

    С нами с:
    11 дек 2007
    Сообщения:
    1.344
    Симпатии:
    0
    если "с повторением" то и 111, 112 и так далее, видимо, тоже.
     
  5. crazyb0y

    crazyb0y Активный пользователь

    С нами с:
    22 июн 2009
    Сообщения:
    20
    Симпатии:
    0
    попробуй рекурсию.
     
  6. topas

    topas Активный пользователь

    С нами с:
    16 авг 2006
    Сообщения:
    2.258
    Симпатии:
    36
    PHP:
    1. <?php
    2. class Variant{
    3.         private $array;
    4.  
    5.         private $i = 0;
    6.         private $size;
    7.         private $self = array();
    8.         private $done = false;
    9.  
    10.         static public $count = 0;
    11.         static public $swapCount = 0;
    12.  
    13.         public function __construct(&$array){
    14.                 self::$count++;
    15.                 $this->array = &$array;
    16.                 $this->size = count($array);
    17.                 $size = $this->size;
    18.                 $this->i = 1;
    19.                 while($size){
    20.                         $this->i *= $size--;
    21.                 }
    22.                 $this->self = array_keys($this->array);
    23.         }
    24.  
    25.         public function next(){
    26.                 if ($this->done) return;
    27.  
    28.                 for ($i = $this->size - 2; $i >= 0; --$i){
    29.                         if ($this->self[$i] < $this->self[$i+1]){
    30.                                 $j = $this->size;
    31.                                 while ($this->self[--$j] < $this->self[$i]);
    32.                                 $this->swap($i, $j);
    33.                                 $l = $this->size - 1;
    34.                                 for ($k = $i + 1; $l > $k; $k++, $l--){
    35.                                         $this->swap($k, $l);
    36.                                 }
    37.                                 return;
    38.                         }
    39.                 }
    40.                 if ($i < 0) $this->done = true;
    41.         }
    42.         public function has(){
    43.                 return !$this->done;
    44.         }
    45.         private function swap($i, $j){
    46.                 self::$swapCount++;
    47.                 $tmp = $this->self[$i];
    48.                 $this->self[$i] = $this->self[$j];
    49.                 $this->self[$j] = $tmp;
    50.  
    51.                 $tmp = $this->array[$i];
    52.                 $this->array[$i] = $this->array[$j];
    53.                 $this->array[$j] = $tmp;
    54.         }
    55. }
    56.  
    57. $array = array(1, 2, 3);
    58. for ($v = new Variant($array); $v->has(); $v->next()){
    59.         print_r($array);
    60. }
    61.  
    а вообще попробуй погуглить next_permutation
     
  7. kostyl

    kostyl Guest

    на algolist.mamual.ru всё есть, правда не на php но все алгритмы основные можно там найти...