@JohnDidact
Нуб во всём

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

Есть строка из определённых уникальных символов, нужно получить все возможные уникальные последовательности из этих символов, в том числе, исключая каждый символ. Вхождение символа в строке от нуля до одного раза. Позиция символа в строке не играет роли в уникальности, то есть 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 строк))? Как рассчитать количество возможных строк, удовлетворяющих моему условию... имею ввиду формулу математическую?
  • Вопрос задан
  • 88 просмотров
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Некорректная формулировка задачи. Из любого непустого набора символов можно сформировать бесконечное количество уникальных строк. 'V', 'VV', 'VVV', ..., продолжать можно до бесконечности.
Если ограничить максимум одним вхождением символа в строку результата, то получится 2n строк, где 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'
Ответ написан
@JohnDidact Автор вопроса
Нуб во всём
В общем, сделал так:
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;
}


Если у кого есть решение быстрее и менее ресурсоёмко, то обязательно напишите мне.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
zagayevskiy
@zagayevskiy
Android developer at Yandex
Число перестановок из n элементов равно n! Считай, сколько это будет, явно не 49.
Со знанием того, что это называется перестановкой алгоритм гуглится в два счёта. Модифицировать его для себя сможешь сам.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Технология Тюмень
от 50 000 до 130 000 ₽
АКМЭ сервис Санкт-Петербург
от 120 000 до 150 000 ₽
03 авг. 2020, в 15:19
5000 руб./за проект
03 авг. 2020, в 15:13
7000 руб./за проект
03 авг. 2020, в 15:06
10000 руб./за проект