Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 181 / 41
Регистрация: 13.07.2017
Сообщений: 4,737
Записей в блоге: 14

Создать список фрагментов данного списка

22.03.2019, 19:47. Показов 1791. Ответов 9
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Допустим, есть список целых чисел, например, { 1, 2, 3, 2, 3, 4, 5, 4, 5, 6, 4, 7, 1, 8, 8, 9, 8 }. Нужно создать список фрагментов этого списка по следующим правилам (постараюсь описать правила максимально "вменяемо", чтобы потом не было претензий):
1. Длина списка фрагментов равна длине исходного списка, каждый фрагмент номер i начинается с элемента исходного списка номер i.
2. Если данный элемент единственный (встречается один раз) в исходном списке, он единственный во фрагменте.
3. Если в исходном списке несколько одинаковых элементов, сравниваются следующие за каждым из них, если они также одинаковые, еще следующие и т. д. (следующим за последним считается первый).
4. Фрагмент имеет минимально возможную длину из элементов, следующих подряд за i, такую, чтобы все фрагменты были уникальными.
5. Затраты времени - не больше O(m * n * log(n)), памяти - не больше O(m * n), где m - максимальная длина фрагмента.
Например, из вышеупомянутого списка получится вот что: { { 1, 2 }, { 2, 3, 2 }, { 3, 2 }, { 2, 3, 4 }, { 3, 4 }, { 4, 5, 4 }, { 5, 4 }, { 4, 5, 6 }, { 5, 6 }, { 6 }, { 4, 7 }, { 7 }, {1, 8 }, { 8, 8 }, { 8, 9 }, { 9 }, { 8, 1 } }. Пояснения:
{ 6 }, { 7 }, { 9 } - эти элементы в списке единственные, поэтому в их фрагменты уже ничего не нужно добавлять.
{ 3, 2 }, { 3, 4 } - тройки общие, а 2 и 4 отличаются, поэтому фрагмент состоит из двух элементов.
{ 2, 3, 2 }, { 2, 3, 4 } - тут два элемента общие, поэтому для уникальности фрагмента требуется третий.
{ 4, 5, 4 }, { 4, 5, 6 }, { 4, 7 } - семерка отличается от обеих пятерок, поэтому третий элемент не нужен, а вот пятерки совпадают, поэтому нужен третий элемент.
{ 8, 8 } - фрагмент может состоять и из одинаковых элементов.
{ 8, 1 } - за последним элементом списка следует первый.
Linq допускается и даже приветствуется.
Возможно ли это?

Добавлено через 16 минут
Мне вот интересно, почему все видят мою тему и проходят мимо? Я же спросил: "Возможно ли это?" - если невозможно, так и напишите, и объясните, почему. Или я опять невнятно сформулировал вопрос? Тогда попросите уточнить. Но просто ноль реакции - это бесит меня. Я же не тролль какой-нибудь, которого все стремятся игнорировать...
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.03.2019, 19:47
Ответы с готовыми решениями:

Как создать “Список списка” из данного задания?
Дано задание "Дан список списков групп, где каждый список группы состоит из записей содержащих фамилии и баллы за экзамен по предмету...

Создать список L2, являющийся копией списка L1, начинающегося с данного узла
Написать функцию, которая создает список L2, являющийся копией списка L1, начинающегося с данного узла.

DOM-узел. Создать элемент, получить список всех стилей, вывести список в внутрь данного елемента
Создать элемент `p`. По своему усмотрению задать стили (не меьше 4 параметров). Получить список всех стилей элемента (в формате...

9
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 181 / 41
Регистрация: 13.07.2017
Сообщений: 4,737
Записей в блоге: 14
23.03.2019, 11:18  [ТС]
Ну, что напишете? У вас жизненная позиция такая - игнорировать именно меня? Чем я вам не угодил? Причем ВСЕМ?! Можете ответить прямо, а не томить молчанием?
0
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
23.03.2019, 17:31
Etyuhibosecyu,
служебные классы:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    /// <summary>
    /// Список для каждой цифры
    /// </summary>
    class DigitList
    {
        public int this[int i]
        {
            get => List[i];
            set
            {
                List[i] = value;
            }
        }
        public int Count => List.Count;
        List<int> List { get; set; }
        /// <summary>
        /// Позиция в основном списке
        /// </summary>
        public int StartIndex { get; set; }
        public int Offset { get; set; }
        /// <summary>
        /// Позиция в служебном списке
        /// </summary>
        public int Index { get; set; }
        public DigitList(int value0, int start, int index)
        {
            StartIndex = start;
            Index = index;
            List = new List<int>();
            Add(value0);
        }
        public void Add(int value)
        {
            List.Add(value);
        }
    }
    class ListComparer: IEqualityComparer<DigitList>
    {
        public bool Equals(DigitList l1, DigitList l2)
        {
            if (l1.Count != l2.Count) return false;
            for (int i = 0; i < l1.Count;)
            {
                if (l1[i] != l2[i++]) return false;
            }
            return true;
        }
        public int GetHashCode(DigitList l)
        {
            int hash = 0;
            for(int i = 0;i<l.Count;i++) hash ^= l[i];
            return hash;
        }
    }

Метод, возвращающий массив списков исходя из начального списка
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
        static List<int>[] NewList(List<int> l0)
        {
            var l = new List<int>[l0.Count];
            // определить количество каждого элемента
            var digitsPos = l0.Distinct().Select(x =>
            (x, l0.Select((y, i) => (y, i)).Where(z => z.Item1 == x).Select(t => t.Item2))); // пара цифра - список индексов
            // создать отдельные списки для каждого числа 
            List<List<DigitList>> list2 = new List<List<DigitList>>(); // служебный список
            IEnumerable<IGrouping<DigitList, DigitList>> gSame;
            foreach (var digit in digitsPos) // пройти по всем числам 
            {
                list2.Add(new List<DigitList>());
                var last = list2.Last();
                int i = 0;
                // первичная инициализация
                foreach (var pos in digit.Item2) // пройти по всем позициям числа
                {
                    last.Add(new DigitList(l0[pos], pos, i++));
                }
                // пока есть группы с одинаковыми списками
                while ((gSame = last.GroupBy(x => x, new ListComparer()).Where(g => g.Count() > 1)).Count() > 0)
                {
                    // пройти по всем группам
                    foreach(var group in gSame)
                    {
                        // пройти по всем спискам внутри группы
                        foreach(var list in group)
                        {
                            last[list.Index].Add(
                                l0[(list.StartIndex + ++last[list.Index].Offset)%l0.Count]); // замкнутость
                        }
                    }
                }
            }
            for (int i = 0; i < l0.Count; i++) l[i] = new List<int>();
            foreach(var list in list2.SelectMany(x=>x))
            {
                for(int i = 0;i<list.Count;i++)
                {
                    l[list.StartIndex].Add(list[i]);
                }
            }
            return l;
        }
    }
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
Затраты времени - не больше O(m * n * log(n))
насчет этого надо еще подумать
1
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 181 / 41
Регистрация: 13.07.2017
Сообщений: 4,737
Записей в блоге: 14
23.03.2019, 17:44  [ТС]
alexus5, спасибо за ответ. Ваш код, мягко говоря, впечатляет. Но ЧЕТЫРЕ вложенных цикла - это время выполнения явно не O(m * n * log(n)).

Добавлено через 42 секунды
Хотя попробую применить и посмотрю на время выполнения.
0
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
23.03.2019, 19:09
Лучший ответ Сообщение было отмечено Etyuhibosecyu как решение

Решение

Etyuhibosecyu, вот вариант по-проще
служебный класс:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    class ListComparer2: IEqualityComparer<List<int>>
    {
        public bool Equals(List<int> l1, List<int> l2)
        {
            if (l1.Count != l2.Count) return false;
            for (int i = 0; i < l1.Count;)
            {
                if (l1[i] != l2[i++]) return false;
            }
            return true;
        }
        public int GetHashCode(List<int> l)
        {
            int hash = 0;
            for (int i = 0; i < l.Count; i++) hash ^= l[i];
            return hash;
        }
    }

и метод
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        static List<int>[] NewList2(List<int> l0)
        {
            var list = new List<int>[l0.Count];
            IEnumerable<IGrouping<List<int>, (List<int>, int, int)>> gr;
            var list0 = l0.Select((x,i) => (new List<int>(), i, 0)).ToArray();
            while((gr = list0.GroupBy(x=>x.Item1, new ListComparer2()).Where(g=>g.Count()>1)).Count()>0)
            {
                foreach(var digit in gr.SelectMany(x=>x))
                {
                    list0[digit.Item2].Item1.Add(l0[(digit.Item2 + digit.Item3) % l0.Count]);
                    list0[digit.Item2].Item3++;
                }
            }
            return list0.Select(x => x.Item1).ToArray();
        }
1
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 181 / 41
Регистрация: 13.07.2017
Сообщений: 4,737
Записей в блоге: 14
23.03.2019, 19:15  [ТС]
Цитата Сообщение от alexus5 Посмотреть сообщение
вот вариант по-проще
А вы проверяли, он рабочий?

Добавлено через 3 минуты
alexus5, похоже, первый вариант действительно имеет именно такую сложность. Типичный список длиной 30000 обрабатывает за 8-12 секунд, а если много похожих фрагментов - за 2-3 минуты.
0
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
23.03.2019, 19:19
Цитата Сообщение от Etyuhibosecyu Посмотреть сообщение
он рабочий?
работает, надо еще протестить на время
0
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
23.03.2019, 19:40
Etyuhibosecyu, у второго линейно относительно размера входного списка. у первого экспоненциально)
Миниатюры
Создать список фрагментов данного списка  
0
Труд вопреки насмешкам
 Аватар для Etyuhibosecyu
430 / 181 / 41
Регистрация: 13.07.2017
Сообщений: 4,737
Записей в блоге: 14
23.03.2019, 19:41  [ТС]
alexus5, у меня ругается на эту строку:
Цитата Сообщение от alexus5 Посмотреть сообщение
list0[digit.Item2].Item3++;
Не удалось изменить возвращаемое значение "List<(List<int>, int i, int)>.this[int]", т.*к. оно не является переменной.
0
28.03.2019, 09:17

Не по теме:

Самое время новый язык начать изобретать, где таких ошибок не будет.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
28.03.2019, 09:17
Помогаю со студенческими работами здесь

Функция, возвращающая список состоящий из элементов данного списка + n последних элементов списка
определить функцию принимающую в качестве параметров список символов и число и возвращающую в качестве результата конкатенцию исходного...

Новый список из n элементов данного списка
Написать программу в двух стилях императивном и итерационном ,Формировующую список, состоящий из не более чем N элементов исходного списка....

List.map (на основе данного списка получить новый список)
Получить список из последних цифр чисел, содержащихся в исходном списке

Из данного одноуровнего списка построить список списков его элементов
Напишите функцию, которая из данного одноуровнего списка строит список списков его элементов, например, (a b) -&gt; ((a) (b)). ...

Создать список из элементов первого списка, которые не входят в другой список
создать список L ,который включает в себя по одному разу елементы,которые входят в список L1 и не входят в список L2


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru