1

Тема: Генерація послідовностей

Всім привіт.
Є задача наступного рівня. На вхід подається масив символів та довжина рядка. Для прикладу

$sumbols = [0, 1, 2]; // 3 символи
$len = 2; // довжина

На виході ми отримуємо комбінації

    [0] => 00
    [1] => 01
    [2] => 02
    [3] => 10
    [4] => 11
    [5] => 12
    [6] => 20
    [7] => 21
    [8] => 22

Це уже є готове. Але ось яка є задача.
Необхідна функція яка буде дуже швидко генерувати тільки 1ну комбінацію.
На вхід подаємо наступне.

$sumbols = [0, 1, 2]; // 3 символи
$len = 2; // довжина
$index = 7; // індекс нашої комбінації

на виході отримуємо 21

Тобто як зробити швидкий алгоритм отримання комбінації по її ідішці.
Враховуємо що у нас масив символів і довжина не змінюється.

Фактично мені треба вивести  матиматичну формулу для цього всього) але як - поки-що хз

Дякую всім ;)

Подякували: leofun011

2 Востаннє редагувалося koala (01.07.2014 11:33:23)

Re: Генерація послідовностей

Підказка: нехай

$symbols = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

тоді

    [0] => 00
    [1] => 01
..
    [98] => 98
    [99] => 99
ще не бачите?

Запишемо номер в системі счислення з основою count($symbols), причому кожна цифра буде представлена відповідним елементом з symbols. От, власне, і все. Якщо зовсім ліньки розбиратися - є base_convert (але його ще адаптувати треба і розмір symbols обмежений), якщо не зовсім - номер діліть на count($symbols) і запам'ятовуйте залишки, вони будуть становити номери символів в зворотньому порядку.
Подякували: leofun011

3

Re: Генерація послідовностей

Підказка помогла в плані напрямку думок. Але трохи не так виходить. Якщо у вас є 10 симолів тоді все вірно. А якщо у вас 5 символів або якась інша кількість:

Ось для символів 01234

Прихований текст

    [0] => 00
    [1] => 01
    [2] => 02
    [3] => 03
    [4] => 04
    [5] => 10
    [6] => 11
    [7] => 12
    [8] => 13
    [9] => 14
    [10] => 20
    [11] => 21
    [12] => 22
    [13] => 23
    [14] => 24
    [15] => 30
    [16] => 31
    [17] => 32
    [18] => 33
    [19] => 34
    [20] => 40
    [21] => 41
    [22] => 42
    [23] => 43
    [24] => 44

4

Re: Генерація послідовностей

Все правильно, це п'ятерична с.ч.

5

Re: Генерація послідовностей

хм. Для прикладу у мене є  така штука.
[14] => 24
З індексом 14 я маю знайти число 2 і 4
тобто вхідні дані виходять такі:
індекс  = 14, номер в рядку => 1, довжина рядка => 2, кількість символів 5 === на виході отримаємо 2
індекс  = 14, номер в рядку => 2, довжина рядка => 2, кількість символів 5 === на виході отримаємо 4

тут ще така штука що може бути не 01234 а ABCE і тд) ну фактично все рівно, так як мені треба знаходити індекс

Пробую ділити так як ви кажете, поки-що  не виходить.

6

Re: Генерація послідовностей

Для 14 і 5:
14 / 5 = 2 (зал. 4)
2 / 5 = 0 (зал. 2)
Записуємо в зворотньому порядку 24 - ось і відповідь.
Складніший приклад. Число 634, основа 7 (оскільки 634>343, має бути 4 знаки):
634 / 7 = 90 (зал. 4)
90 / 7 = 12 (зал. 6)
12 / 7 = 1 (зал. 5)
1 / 7 = 0 (зал. 1)
відповідь 1564. Перевіряємо: 1*343 + 5*49 + 6*7 + 4*1 = 634.

Подякували: funivan, leofun012

7

Re: Генерація послідовностей

Ура ура ура) все паше ;) щиро дякую

кусок коду ;)

Прихований текст

 public function getFromIndex($stringIndex, $stringLen) {
      $symbolsNum = count($this->symbols);

      $indexes = [];
      $prev = $stringIndex;

      while ($stringLen > 0) {
        $result = $prev % $symbolsNum;
        $prev = $prev / $symbolsNum;

        if (!isset($this->symbols[$result])) {
          throw new \Exception("Invalid symbol index:" + $result);
        }
        $indexes[] = $this->symbols[$result];
        $stringLen--;
      }
      $indexes = array_reverse($indexes);

      return implode("", $indexes);
    }

8

Re: Генерація послідовностей

Ах не вспів(((