уникальность цифрового ряда

[RaZum]

Есть набор из 9 цифр (не чисел!), 1-9, например строка "245679813"
Как проще проверить их уникальность? (т.е. отсутствие повторений)

Прямой перебор со сравнением оставшихся - это понятно.
Есть вариант через контроль суммы и перемножения.
С регулярными выражениями нужно видимо делать откаты, хотя как-то сложно и громоздко.

 

[Andrey_A]

С регулярными выражениями

Сумма чисел от 1 до 9 всегда 45

$sLine='245679813'
$Sum=Execute(StringRegExpReplace($sLine,'(.)(?<!\z)','${1}+'))
MsgBox(4096,'$Summ',$Sum)

 

[RaZum]

"123456789" = 45
"122556699" = 45
Лучше уж тогда перемножение

 

[Andrey_A]

Лучше уж тогда перемножение

Я лишь дал пример в одну строку, там может быть и такой вариант

$sLine='987654321'
$Sum=Execute(StringRegExpReplace($sLine,'(.)(?<!\z)','${1}*'))
If StringLen($sLine)=9 And Execute(StringRegExpReplace($sLine,'(.)(?<!\z)','${1}+'))=45 And Execute(StringRegExpReplace($sLine,'(.)(?<!\z)','${1}*'))=362880 Then
 MsgBox(4096,'Да',$sLine)
Else
 MsgBox(4096,'Нет',$sLine)
EndIf

Можно и такие:

; $sLine='123456789'
$sLine='162255669'
$sLine=StringRegExpReplace($sLine,'(.)(?=.*\1)','')
; $sLine=StringRegExpReplace($sLine,'([1-9])(?=.*\1)','')
$n=@extended
MsgBox(4096,'$sLine',$sLine)
MsgBox(4096,'$n',$n)

; $sLine='123456789'
$sLine='162255669'
If StringLen($sLine)<>9 OR StringRegExp($sLine,'[^1-9]') Then
  MsgBox(4096,'NOT',$sLine)
Else
  $sLine=StringRegExpReplace($sLine,'([1-9])(?=.*\1)','')
  $n=@extended
  MsgBox(4096,'$sLine',$sLine)
  MsgBox(4096,'$n',$n)
EndIf

 

[Alecsis]

И даже так:

Opt('MustDeclareVars', True)
Local _
  $aCount[10] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], _
  $sLine, $iDigit, $bRepeat, $i
;
$bRepeat = False
$sLine='162255669'
;~ $sLine='987654321'
;
If Not StringRegExp($sLine,'^\d+$') Then
  MsgBox(16, 'Уникальность', 'Некорректная исх. строка')
  Exit
EndIf
For $i = 1 To StringLen($sLine)
  $iDigit  = Number(StringMid($sLine, $i, 1), 1)
  $bRepeat = ($aCount[$iDigit] > 0)
  If $bRepeat Then ExitLoop
  $aCount[$iDigit] += 1
Next
;
MsgBox(($bRepeat ? 48 : 64), 'Уникальность', _
       $sLine & ($bRepeat ?' – eсть повторы!' : ' – Ok, нет повторов'))
Exit

При желании можно добавить доп. «блок-посты», чтобы строка была строго из 9 символов, не содержала "0" итп.
А если сильно хочется, то задействовать 16-чные цифры, буквы, да и всё, что угодно — техника по сути та же самая .

 

[Andrey_A]

Если уж через цикл, то используя MAP короче и быстрее

Local $sLine='245679813',$n=0
If StringRegExp($sLine,'^[1-9]{9}$')Then
  Local $mMap[],$aNum=StringSplit($sLine,'')
  For $i=1 To $aNum[0]
    $mMap[$aNum[$i]]+=1
  Next
  $n=UBound($mMap)
EndIf
MsgBox(4096,$n=9? 'YES':'NOT',$sLine)

 

[RaZum]

Все окончательные варианты работают, все показывают одинаковое количество ошибок при выборке из 100.000 слов (9 элементов 0-9). Паралельно проверял прямым перебором "в лоб".
Для возможности сравнения, в вариант со StringMid, добавил в условие .. Or $iDigit = 0 ..
Вообщем, самый быстрый способ, как я и предпологал, оказался через регулярные выражения, а самый медленный - посимвольный перебор (StringMid). Про перебор "в лоб" и так понятно.
Кому интересно, результаты (только у меня) примерно такие:
(проверка массива строк, с заполнением массива уникальными строками - при рандоме уникальных мало)
2,9 - StringRegExpReplace
4,1 - Map
8,5 - StringMid
Для сравнения - заполнение массива с помощью "random" в цикле - 4,6
Прямой перебор вышел за 15, но у него и задача посложнее и сам способ медленный.

Всем спасибо за помощь.

 

[Andrey_A]

2,9 - StringRegExpReplace

Это очевидно, но на каком StringRegExpReplace тестировалось?, если на этом
$sLine=StringRegExpReplace($sLine,'(.)(?=.*\1)','')
То можно поставить в конце 1 - одна замена - будет на чуть-чуть ещё быстрее))
$sLine=StringRegExpReplace($sLine,'([1-9])(?=.*\1)',0,1)
Хотя там можно просто
StringRegExp($sLine,'([1-9])(?=.*\1)')

 

[RaZum]

Эта строка

$sLine = StringRegExpReplace ($sLine,'([1-9])(?=.*\1)','')

Сообщение автоматически объединено: 3 Мар 2023

Забыл упомянуть о сложении и перемножении

459491724 / 415297449 / 724915449 / 297149544 ...

 

[Andrey_A]

Забыл упомянуть о сложении и перемножении

А подробнее - мне тоже интересны математические задачи - недавно занимался суммой цифр чисел для любых чисел в диапазоне (типа метода Гаусса)
----
Я понял о каком суммировании/перемножении идёт речь - вопрос снимается, я думал там более глубокая задача после опрделения валидности...

 

[RaZum]

В самом начале я упоминал о сумме и о перемножении, как о простом варианте валидации строки.
Сумма 1-9 = 45, а произведение 362880
Так вот это числа которые дают теже результаты, но при этом имеют повторения.
Т.е. даже двойной контроль провалился.

Сообщение автоматически объединено: 3 Мар 2023

По коррекции

$sLine=StringRegExpReplace($sLine,'([1-9])(?=.*\1)',0,1)

2,7 - по ошибкам тоже нормально

 

[Oki]

Как проще проверить их уникальность? (т.е. отсутствие повторений)

Уникальность кого и где? Последовательностей из 9 цифр среди других последовательностей? Или тест на то, что нет одинаковых цифр в одной последовательности?

Сообщение автоматически объединено: 4 Мар 2023

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

Сообщение автоматически объединено: 4 Мар 2023

А если речь именно о тесте на неповторяемость цифр в одной задаваемой последовательности, то достаточно в 10-элементном массиве счётчиков каждой цифры (индекс массива соответствует значению цифры) накапливать количество наблюдений каждой цифры и сообщать о непрохождении теста, как только любой счётчик достигнет двойки (если стартовать от нуля). Алгоритмически вряд ли что-то проще можно предложить. Вот только сам факт выполнения теста в интепретаторе строк в случае с AutoIt может затянуть время проверки за счёт именно повторяющегося разбора тех же строк скрипта вновь и вновь.

 

[RaZum]

Есть набор из 9 цифр (не чисел!): 123456789
Эти цифры можно менять местами в произвольном порядке, и всё на этом.
Проверка нужна чтобы исключить все остальные варианты: иное количество, иные символы, повторы.
По поводу простого перебора "в лоб", уже упоминал. Он медленный (в разы), так как реализация циклов внутри стандартных функций языка, на много быстрее чем в UDF, и по этому нужен способ побыстрее. Регулярные выражения это подтверждают.
Пример простого перебора с пропуском лишних циклов:
(по времени, в тех же условиях - 7,5)

Спойлер

Func Example ($sLine)
   Local $a = StringSplit ($sLine, "")
   If $a[0] = 9 Then
      For $i = 1 To 9
         For $j = 1 To 9
            If $a[$j] = $i Then ContinueLoop 2
         Next
         Return SetError (2, $i, 0)      ; какая цифра отсутствует 
      Next
      Return $sLine                   ;  валидный набор
   EndIf
   Return SetError (1, $a[0], 0)      ; иное количество
EndFunc

Надеюсь ничего не пропустил

 

[Oki]

Цикл в цикле не нужен.

достаточно в 10-элементном массиве счётчиков каждой цифры (индекс массива соответствует значению цифры) накапливать количество наблюдений каждой цифры и сообщать о непрохождении теста, как только любой счётчик достигнет двойки (если стартовать от нуля)

Один цикл в один проход.

Сообщение автоматически объединено: 5 Мар 2023

Например, так.

Dim $a[10] = [9, 3, 2, 1, 4, 5, 6, 9, 8, 7]
Dim $aiFound[10] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
$iFlag = 0
$i = 1
While $iFlag = 0 And $i < 10
    If $aiFound[$a[$i]] = 0 Then
        $aiFound[$a[$i]] = 1
        $i += 1
    Else
        $iFlag = 1
    EndIf
WEnd
MsgBox(4096, "0 stands for valid, 1 does for invalid", $iFlag)

 

[RaZum]

$i = 1 - это под набор из 9 элементов видимо, но при этом 0 валидный

 

[Oki]

$i = 1 - это под набор из 9 элементов видимо, но при этом 0 валидный

Из постановки задачи и дальнейшего считывания в массив $a следует, что под нулевым индексом этого массива окажется число 9, а под остальными 9 индексами - 9 целых чисел из интервала от 1 до 9 каждое, а при этом требуется установить, есть ли среди этих 9 элементов повторения, с чем этот скрипт и справляется на примере последовательности цифр "321456987" (и вообще, на всех 387420489 последовательностях, удовлетворяющих условию задачи после их аналогичного считывания в $a вместо первой строки скрипта).