Как получить все возможные уникальные строки из определённых символов?

Question

[John Didact]

Есть строка из определённых уникальных символов, нужно получить все возможные уникальные последовательности из этих символов, в том числе, исключая каждый символ. Вхождение символа в строке от нуля до одного раза. Позиция символа в строке не играет роли в уникальности, то есть VUCADE и DAVUCE - это одинаковые строки. Решил писать функцию, писал, пока в голову ни пришла мысль - "а вдруг я изобретаю велосипед???". На скорую руку набросал:

// $str - набор сиволов
// $withoutNum - количество исключённых символов
// $arr - ссылка на массив, куда буду записывать комбинации строк
// $idling  - количество "порожняковых" работ
function combinations($str, $withoutNum, &$arr, &$idling = 0){
 $len = strlen($str);  // длина строки
 $withoutPos = 0;      // позиция исключённого символа
 if(!$str or ($withoutPos > $len) or($withoutNum + $withoutPos >= $len)) return;
 while($len--){
  $nstr = substr($str, 0, $withoutPos) . substr($str, $withoutPos + $withoutNum);
  if(isset($arr[$nstr])) $idling++;
  else {
   $arr[$nstr] = true; // запишу строку в индекс, чтобы было легче найти
   combinations($nstr, $withoutNum + 1, $arr, $idling);
  }
  if($withoutPos++ + $withoutNum === 0) break;
 }
 combinations($str, $withoutNum + 1, $arr, $idling);
}

$str = 'VUCADE';
combinations($str, 0, $arr, $idling);
$str_list = array_keys($arr); // тут будет список полученных строк

var_dump($str_list);

array(49) {
  [0]=>
  string(6) "VUCADE"
  [1]=>
  string(5) "UCADE"
  [2]=>
  string(3) "ADE"
  [3]=>
  string(3) "UDE"
  [4]=>
  string(3) "UCE"
  [5]=>
  string(3) "UCA"
  [6]=>
  string(4) "UCAD"
  [7]=>
  string(1) "D"
  [8]=>
  string(1) "U"
  [9]=>
  string(2) "UC"
  [10]=>
  string(2) "DE"
  [11]=>
  string(2) "UE"
  [12]=>
  string(1) "E"
  [13]=>
  string(5) "VCADE"
  [14]=>
  string(3) "VDE"
  [15]=>
  string(3) "VCE"
  [16]=>
  string(3) "VCA"
  [17]=>
  string(4) "VCAD"
  [18]=>
  string(1) "V"
  [19]=>
  string(2) "VC"
  [20]=>
  string(2) "VE"
  [21]=>
  string(5) "VUADE"
  [22]=>
  string(3) "VUE"
  [23]=>
  string(3) "VUA"
  [24]=>
  string(4) "VUAD"
  [25]=>
  string(2) "VU"
  [26]=>
  string(5) "VUCDE"
  [27]=>
  string(3) "CDE"
  [28]=>
  string(3) "VUC"
  [29]=>
  string(4) "VUCD"
  [30]=>
  string(5) "VUCAE"
  [31]=>
  string(3) "CAE"
  [32]=>
  string(3) "VAE"
  [33]=>
  string(4) "VUCA"
  [34]=>
  string(1) "A"
  [35]=>
  string(2) "AE"
  [36]=>
  string(5) "VUCAD"
  [37]=>
  string(3) "CAD"
  [38]=>
  string(3) "VAD"
  [39]=>
  string(3) "VUD"
  [40]=>
  string(2) "AD"
  [41]=>
  string(2) "VD"
  [42]=>
  string(4) "CADE"
  [43]=>
  string(1) "C"
  [44]=>
  string(2) "CA"
  [45]=>
  string(4) "VADE"
  [46]=>
  string(2) "VA"
  [47]=>
  string(4) "VUDE"
  [48]=>
  string(4) "VUCE"
}

Так вот... Есть что побыстрее (моя функция вычислила 143 повторяющихся строки) и надёжней ((для строки VUCADE, то есть, для 6-ти символов, у меня вышло 49 строк))? Как рассчитать количество возможных строк, удовлетворяющих моему условию... имею ввиду формулу математическую?

Answer 1

[Rsa97]

Некорректная формулировка задачи. Из любого непустого набора символов можно сформировать бесконечное количество уникальных строк. 'V', 'VV', 'VVV', ..., продолжать можно до бесконечности.
Если ограничить максимум одним вхождением символа в строку результата, то получится 2ⁿ строк, где n - количество уникальных символов. Каждому символу можно сопоставить один бит двоичного числа. Если символ входит в очередную строку, то бит равен 1, если не входит, то 0.

VUCADE

00 - 000000 - ''
01 - 000001 - 'E'
02 - 000010 - 'D'
03 - 000011 - 'DE'
04 - 000100 - 'A'
05 - 000101 - 'AE'
06 - 000110 - 'AD'
07 - 000111 - 'ADE'
08 - 001000 - 'C'
09 - 001001 - 'CE'
10 - 001010 - 'CD'
11 - 001011 - 'CDE'
12 - 001100 - 'CA'
13 - 001101 - 'CAE'
14 - 001110 - 'CAD'
15 - 001111 - 'CADE'
16 - 010000 - 'U'
17 - 010001 - 'UE'
18 - 010010 - 'UD'
19 - 010011 - 'UDE'
20 - 010100 - 'UA'
21 - 010101 - 'UAE'
22 - 010110 - 'UAD'
23 - 010111 - 'UADE'
24 - 011000 - 'UC'
25 - 011001 - 'UCE'
26 - 011010 - 'UCD'
27 - 011011 - 'UCDE'
28 - 011100 - 'UCA'
29 - 011101 - 'UCAE'
30 - 011110 - 'UCAD'
31 - 011111 - 'UCADE'
32 - 100000 - 'V'
33 - 100001 - 'VE'
34 - 100010 - 'VD'
35 - 100011 - 'VDE'
36 - 100100 - 'VA'
37 - 100101 - 'VAE'
38 - 100110 - 'VAD'
39 - 100111 - 'VADE'
40 - 101000 - 'VC'
41 - 101001 - 'VCE'
42 - 101010 - 'VCD'
43 - 101011 - 'VCDE'
44 - 101100 - 'VCA'
45 - 101101 - 'VCAE'
46 - 101110 - 'VCAD'
47 - 101111 - 'VCADE'
48 - 110000 - 'VU'
49 - 110001 - 'VUE'
50 - 110010 - 'VUD'
51 - 110011 - 'VUDE'
52 - 110100 - 'VUA'
53 - 110101 - 'VUAE'
54 - 110110 - 'VUAD'
55 - 110111 - 'VUADE'
56 - 111000 - 'VUC'
57 - 111001 - 'VUCE'
58 - 111010 - 'VUCD'
59 - 111011 - 'VUCDE'
60 - 111100 - 'VUCA'
61 - 111101 - 'VUCAE'
62 - 111110 - 'VUCAD'
63 - 111111 - 'VUCADE'

Comments

[John Didact]

Да, я имел ввиду одно вхождение - максимум. Подправил.

Как Вы уникальную последовательность бит из всех возможных вычитали?

[Rsa97]

John Didact, Я ничего не вычитал. Если перебрать все числа от 0 до 2ⁿ-1, то их двоичное представление даст все возможные комбинации битов.

[John Didact]

Rsa97, в двоичной системе, имеете ввиду?

[John Didact]

Rsa97, туплю) всё, всё, понял)) в ответе Вы не просто так указали обычные (десятичные) числа… спасибо большое.

[John Didact]

Rsa97, добрался до компа, сделал так:

function shit(string $str){                      // Принимаю строку.
 $len = mb_strlen($str);                         // Длина строки,
 $num = 2 ** $len - 1;                           // количество возможных строк.
 return array_map(function($n) use($len,$str){   // Обрабатываю массив чисел (от нуля до кол-ва возможных строк), используя длину исходной строки и саму строку:
     $value = '';                                // Значение новой строки по умолчанию,
     $bin = sprintf("%0{$len}b",$n);             // бинарное представление десятичного числа, заполненное влево до длины исходной строки,
     for($i = 0; isset($bin[$i]); $i++){         // прохожу по кадому символу в $bin:
      $bin[$i] and $value .= $str[$i];           // если итерируемый символ - истина, то записываю в новую строку символ из сходной строки с ключём, равным активной итерации.
     }
     return $value;
 },range(0, $num));
}

$dogShit = shit('VUCADE');

Работает, как надо. Но вопрос возник... Есть реализация по проще для системы/сервера/PHP? "По проще" - имею ввиду экономие времени и памяти на операцию. Вы бы как реализовали подобное?

[John Didact]

Rsa97, ещё подумал только что, что можно не добивать бинарное представление числа нулями слева, а просто проверку делать справа, и если больше символов нет, то переходить к следующей строке. Типа так:

function shit(string $str){                      // Принимаю строку.
 $len = mb_strlen($str);                         // Длина строки,
 $num = 2 ** $len - 1;                           // количество возможных строк.
 return array_map(function($n) use($len,$str){   // Обрабатываю массив чисел (от нуля до кол-ва возможных строк), используя длину исходной строки и саму строку:
     $value = '';                                // Значение новой строки по умолчанию,
     $bin = decbin($n);                          // бинарное представление десятичного числа,
     for($i = 1; isset($bin[-$i]); $i++){        // прохожу по кадому символу в $bin:
      $bin[-$i] and $value = $str[-$i] . $value; // если итерируемый символ - истина, то записываю в новую строку символ из сходной строки с ключём, равным активной итерации.
     }
     return $value;
 },range(0, $num));
}

Как думаете, стоит ли?

[John Didact]

Rsa97, ещё в голову пришло... Зачем мне массив чисел, если можно просто циклом пройтись?) Пойду переписывать)

[John Didact]

John Didact,

function shit(string $str){                      // Принимаю строку.
 $len = mb_strlen($str);                         // Длина строки,
 $num = 2 ** $len - 1;                           // количество возможных строк,
 $listStr = array();                             // список всех возможных строк.
 do{
  $value = '';                                   // Значение новой строки по умолчанию,
  $bin = decbin($num);                           // бинарное представление десятичного числа,
  for($i = 1; isset($bin[-$i]); $i++){           // прохожу по кадому символу в $bin:
   $bin[-$i] and $value = $str[-$i] . $value;    // если итерируемый символ - истина, то записываю в новую строку символ из сходной строки с ключём, равным активной итерации.
  }
  $listStr[] = $value;
 } while($num--);
 return $listStr;
}

Answer 2

[John Didact]

В общем, сделал так:

function shit(string $str){                      // Принимаю строку.
 $len = mb_strlen($str);                         // Длина строки,
 $num = 2 ** $len - 1;                           // количество возможных строк,
 $listStr = array();                             // список всех возможных строк.
 do{
  $value = '';                                   // Значение новой строки по умолчанию,
  $bin = decbin($num);                           // бинарное представление десятичного числа,
  for($i = 1; isset($bin[-$i]); $i++){           // прохожу по кадому символу в $bin:
   $bin[-$i] and $value = $str[-$i] . $value;    // если итерируемый символ - истина, то записываю в новую строку символ из сходной строки с ключём, равным активной итерации.
  }
  $listStr[] = $value;
 } while($num--);
 return $listStr;
}

Если у кого есть решение быстрее и менее ресурсоёмко, то обязательно напишите мне.

Answer 3

[Денис Загаевский]

Число перестановок из n элементов равно n! Считай, сколько это будет, явно не 49.
Со знанием того, что это называется перестановкой алгоритм гуглится в два счёта. Модифицировать его для себя сможешь сам.

Comments

[John Didact]

Не уверен, что перестановка это то, что мне нужно. Вычитал, что это "размещение с повторением". Но спасибо, прочту.

[Денис Загаевский]

John Didact, само слово "повторения" противоречит твоему вопросу.

[John Didact]

Денис Загаевский, ну это уже касаемо битов… того, о чём написал тот, чей ответ отмечен решением.

[Денис Загаевский]

John Didact, ты вопросы научись нормально задавать.
" все возможные уникальные последовательности из этих символов" и "Позиция символа в строке не играет роли в уникальности" это вообще разные вещи.