2

Ситуация следующая: пусть имеется массив каких-либо объектов, для простоты возьмём массив символов. Заранее неизвестно, какие в нём символы. Надо каким-либо образом разделить его на несколько массивов, содержащих только одинаковые символы. Например

arr = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']

следовательно, на выходе должно получиться четыре массива:

arr1 = ['a', 'a', 'a']
arr2 = ['b', 'b']
arr3 = ['c', 'c']
arr3 = ['d', 'd']

Или двумерный массив, состоящих из этих массивов

arr = [['a', 'a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd']]

Пробовал делать как-то так

arr = sorted(arr)
a = []
b = []
for i in range(1, len(arr)-1):
   if (arr[i] == arr[i+1]):
       a.append(arr[i])
else:
    b.append(a)
    a = []

Однако в результате получается

[['a'], ['b'], ['c']]

Тут скорее нужна не реализация на Python, а понимание данного алгоритма, вроде бы простая задача, но никак не могу понять, как её решить

2
  • 2
    Нужно именно поделить, или достаточно подсчитать число элементов каждого значения и создать массивы заполненные ими в нужном количестве?
    – Kromster
    2 июл 2018 в 8:55
  • Нет, нужно именно разделить исходный массив на несколько массивов.
    – Alexshev92
    2 июл 2018 в 8:59

4 ответа 4

5
from collections import defaultdict

arr = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']
d = defaultdict(list)

for i in arr:
    d[i].append(i)

print(list(d.values()))  # [['a', 'a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd']]

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

arr = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']

result = []
map_dict = {}  # тут словарь не является промежуточной структурой данных
               # он служит лишь как карта для запоминания позиций списков 
               # в результирующем списке

for i in arr:
    if i in map_dict:
        pos = map_dict[i]
        result[pos].extend(i)
    else:
        pos = len(result)
        map_dict[i] = pos
        result.append([i])

print(result)  # [['a', 'a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd']]
3

Попробуйте groupby:

from itertools import groupby

arr = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']

arr_str = ''.join(sorted(arr))
print(arr_str)  # aaabbccdd

new_arr = [list(values) for _, values in groupby(arr_str)]
print(new_arr)  # [['a', 'a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd']]
5
  • А если без itertools? Я никак не могу понять, как это сделать именно на уровне алгоритма.
    – Alexshev92
    2 июл 2018 в 9:06
  • В соседнем ответе через словарь сделали, подходит? Там используется словарь с значением список -- вот с такой нотацией Dict[Str, List[Str]]. defaultdict помогает по умолчанию подставлять в значение объект списка, если ключа нет
    – gil9red
    2 июл 2018 в 9:07
  • Да, оба ответа правильные, но в них есть некая обертка, я хочу понять, как происходят действия с массивом именно на, грубо говоря, "низком" уровне. Как с помощью только условий и циклов, данную задачу решить. Наверное, несколько расплывчато исходный вопрос сформулировал...
    – Alexshev92
    2 июл 2018 в 9:11
  • 1
    С словарем проще будет объяснить (groupby немного муторный): gist.github.com/gil9red/f0e323cd07c4c12d002e39d6bce6d516
    – gil9red
    2 июл 2018 в 9:15
  • Спасибо! Теперь стало немного понятнее.
    – Alexshev92
    2 июл 2018 в 9:17
2

Если я правильно понял, то, ты хочешь максимально понятный алгоритм

arr = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']
d = {}
for item in arr:
    if item in d:
       d[item].append(item)
    else:
        d[item] = [item]

print(d.values())
0

collections.Counter как специально придуман для решения этой задачи:

import collections

a = ['a', 'b', 'a', 'c', 'b', 'd', 'c', 'a', 'd']

for k, v in collections.Counter(a).items():
    print([k] * v)
['a', 'a', 'a']
['b', 'b']
['c', 'c']
['d', 'd']

Ваш ответ

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

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