0

Как вырезать из массива текста только те строки, в которых любой символ в строке не повторяется, при этом не важно что это за символ и на каких он позициях в строке?

Если универсального алгоритма нет, то тогда как это сделать, зная набор всех символов (буквы, цифры) для всего массива (ряд строк могут не иметь общих символов между собой, но входят в набор символов для всего массива) и длину строк?

Как вариант, можно Python, если это проще. Спасибо

2
  • 3
    На python можно сравнить длину строки и размер множества, полученного из этой строки. Поскольку в множестве элементы не повторяются - длины будут равны только в том случае, когда в строке нет повторяющихся симоволов. (if len(line) == len(set(line)) ... )
    – user247581
    10 авг 2018 в 15:55
  • 2
    Ваш текст - это сплошная строка без обрывов, или с \n\r ? Было бы хорошо дать пример "текста".
    – Hellseher
    10 авг 2018 в 19:53

3 ответа 3

2

Чтобы отфильтровать строки, в которых любые символы повторяются:

#!/usr/bin/env python3
import fileinput

for line in fileinput.input():
    if len(line) == len(set(line)): # all chars in the line are unique
        print(line, end='')

Используется условие для уникальности символов, предложенное @Anton в комментарии.

Пример:

$ echo $'abc\nded\nfghi' | lines-with-uniq-chars
abc
fghi

Это поддерживает и не ascii символы, которые могут более одного байта занимать в текущей кодировке (locale). Это не поддерживает символы состоящие из нескольких Unicode сode points (к примеру, ё -- U+0435 U+308). Если хочется поддерживать такие буквы, то см. Как разбить строку на отдельные символы?

1
  • Класс, ищет в разы быстрей чем баш-хак. Спасибо за ссылочки.
    – Hellseher
    11 авг 2018 в 9:54
2

Hackers delight!

Логически, задача разбивается на

  • подсчитать длину строки
  • подсчитать количество уникальных символов
  • если оба значения равны, вывести строку

./get_line_uniq_chars.sh

#!/usr/bin/env bash

make_strings()
{
    strings /dev/urandom \
        | head -c100k \
        | sed -e ':a;N;$!ba;s/\n//g' -e 's/ //g' -e 's/\t//g' \
        | fold -s -w40
}

get_lines_uniq_chars()
{
    local line_ln
    local uniq_chars

    while read -r line; do
        line_ln="$(echo "$line" | wc -c)"
        uniq_chars="$(echo "$line" \
            | grep -o . \
            | sort -u \
            | paste -s -d '\0' - \
            | wc -c)"

        if [[ "$line_ln" == "$uniq_chars" ]]; then
           echo "$line"
        fi
    done
}

main()
{
    make_strings | get_lines_uniq_chars
}

main "$@"
# End of script

Что получаем, если нужно читать из файла замените функцию make_strings чтением из фала cat "$1" | get_lines_uniq_chars

~$ time  ./get_line_uniq_chars.sh
CBn{|F>1OSpR!j0lkeY%XT]UwPH"gW
,8KbSi6>Y\_7N';fvnXtj+1`@Fgy0)
v0o&}Fmjb7E89K>DHWY2dy_CJf[*Z4
Ly>G7&=(/Q-nOgf;^jKX.2zu`U$'!9
J}]^7nmt16iuWGF4~[Y/"*\yL>rM?A
^!iu1aT4GF_@klnA%$&?BeU";M=<+|
u1{+B8k2z,tVm5Lq6e'AyF~HOGo3<X
plP\mwK5MIVa"<!L7n^UyR3;eC,rqO
M%b'=#[]P`a{.7B!wFZe8QCmg~+I9T
|Hw/~(8!7IO'k`5)$:W-sPCG]r+#L_
[urVw7zJvg.]eO^cQ>~d)Eq<Ka?8%f
zY;}RAi{H~yfqld?Uv5"O\De[+Cg*|
G$I02y7e1KBgqZl:M\*bS~Xus+k}DW
NC1{Yq0ciBD2)\Q<7?]sUhRy!#I6A[
real    0m13.880s
user    0m9.366s
sys     0m17.788s
3
  • u cool ! thx ) работает . А если скажем нужно допустить однократное повторение символа (или максимально возможное N раз), есть мысли, как это можно сделать опционально?
    – TWOfish
    10 авг 2018 в 22:20
  • @Bl0wfish имет значение каких символов? если нет то: если ( длина_строки - количество_допустимых_повторов) == количество_уникальных. Могу дописать как опцию к функции get_lines_uniq_char
    – Hellseher
    10 авг 2018 в 22:43
  • Не имеет значения какого конкретно именно символа допускается повтор, правило должно относится ко всем символам строки. (Если играет какое-то значение - мои символы -буквы англ (и строчные и заглавные)+цифры.)
    – TWOfish
    10 авг 2018 в 22:54
0
def has_dup(strings):
    used = set()
    for letter in string:
        if letter in used:
            return True
        else:
            used.add(letter)
    return False


def only_without_dups(string):
    return [string for string in strings if not has_dup(string)]


# Тестировка

strings = ["Hello, world", "abcdABCD", "abcdAbCD", "xyzXYZ"]
result  = only_without_dups(strings)

print(result)

Вывод:

['abcdABCD', 'xyzXYZ']

Объяснение:

Функция has_dup() собирает использованные символы строки в множестве used и сравнивает всякий последовательный символ со знаками в этом множестве - командой

     if letter in used: 

Когда совпадает, значит, что символ в строке повторился, и функция немедленно завершается, возвращая значение True.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.