ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
25 сообщений из 45, страница 1 из 2
  1  все
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306086
xaoc2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xaoc2
Гость
Срочно ! ( осталось 3 часа ) Нужна реализация вот такого алгоритма:

Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения из списка B.

пример:

Код: plaintext
1.
2.
3.
4.
5.
f(A, B)
A = [ 1 , 2 , 3 , 4 , 5 , 3 , 2 , 4 , 8 , 5 ]
B=[ 5 , 2 , 3 ]
result = a(A, B)
// результат будет 2 так как кратчайшая последовательность
// начинается на второй позиции
...
Рейтинг: 0 / 0
12.06.2011, 23:01
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306097
xaoc2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xaoc2
Гость
Упс... ршибочка, я имелл в виду:
Код: plaintext
1.
2.
3.
.....
result = f(A, B)
...
...
Рейтинг: 0 / 0
12.06.2011, 23:09
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306129
xaoc2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xaoc2
Гость
Извиняюсь:
Код: plaintext
1.
2.
3.
4.
5.
6.
f(A, B)
A = [ 1 , 2 , 3 , 4 , 5 , 3 , 2 , 4 , 8 , 5 ]
B=[ 5 , 2 , 3 ]
result = a(A, B)
// результат будет 5 так как кратчайшая последовательность
// начинается на пятой позиции
...
Рейтинг: 0 / 0
13.06.2011, 00:25
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306139
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
в форум "Работа"
...
Рейтинг: 0 / 0
13.06.2011, 00:39
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306185
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
Больно не проверял но работает вроде.
(отсчет позиции у меня с нуля идет)

Код: plaintext
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.
 public static int GetPositionLeastSequence(int[] A, int[] B)
        {
            int[] check = new int[B.Length];
            int countChecked = 0;
            List<int[]> seqs = new List<int[]>();

            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    if (A[i] == B[j])
                    {
                        check[j] = i;
                        countChecked++;

                        if (countChecked >= B.Length)
                            seqs.Add(check.ToArray());
                    }
                }
            }

            int minLen = A.Length;
            int[] result = null;
            int length = 0;

            for (int i = 0; i < seqs.Count; i++)
            {
                if ((length = seqs[i].Max() - seqs[i].Min()) < minLen)
                {
                    result = seqs[i];
                    minLen = length;
                }
            }

           return result.Min();

        }
...
Рейтинг: 0 / 0
13.06.2011, 02:09
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306208
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
Извини чувак чета я там намудрил.
Код: plaintext
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.
     public static int GetPositionLeastSequence(int[] A, int[] B)
        {
            int[] check = new int[B.Length];
            int countChecked = 0;
            
            int length = A.Length;
            int position = 0;

            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    if (A[i] == B[j])
                    {
                        check[j] = i;
                        countChecked++;

                        if (countChecked >= B.Length)
                        {
                            if (check[j] - check.Min() < length)
                            {
                                position = check.Min();
                                length = check[j] - check.Min();
                            }
                        }
                    }
                }
            }

           return position;

        }
...
Рейтинг: 0 / 0
13.06.2011, 03:37
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306211
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
неверно и неэффективно.

невозможно решать такую задачу без учета ограничений.
...
Рейтинг: 0 / 0
13.06.2011, 03:47
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306212
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

А че неверно то.
...
Рейтинг: 0 / 0
13.06.2011, 03:47
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306215
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
запусти при A = {2, 2, 2, 2}, B = {5, 2}.
...
Рейтинг: 0 / 0
13.06.2011, 04:10
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306216
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

Ну это ты уже придираешься.
Автор просит найти - т.е.
негласное условие что она
уже там есть.
...
Рейтинг: 0 / 0
13.06.2011, 04:12
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306217
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
ок, A = {2, 2, 2, 2, 2, 5}, B = {5, 2}
...
Рейтинг: 0 / 0
13.06.2011, 04:30
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306218
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

Ладно уел.
Ну так покажи уже мастер-класс.
...
Рейтинг: 0 / 0
13.06.2011, 04:42
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306219
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
решение или код?
...
Рейтинг: 0 / 0
13.06.2011, 05:04
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306220
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

ну давай решение
кодом тебя утруждать
как-то неудобно.
...
Рейтинг: 0 / 0
13.06.2011, 05:05
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306221
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
не злись :-)

общий глупый алгоритм, поскольку об ограничениях топикстартер умолчал.
пусть M = B.length(), N = A.length();
отсортируем B;
будем двигать два указателя по массиву A, l и r, изначально l = r = 0;
пусть у нас будет массив C[B.length()] такой, что C[i] выражает количество чисел B[i] на отрезке [l; r];
научимся определять "хорошую" последовательность. для нас это означает, что для любого i из [0; B.length()-1] => C[i] > 0;
научимся по числу определять его номер в массиве B. поскольку он отсортирован, можно воспользоваться бинарным поиском для ускорения процесса (впрочем, собственно для этого мы его и сортировали). теперь мы можем уменьшать / увеличивать количество одинаковых чисел, существующих в B за O(log M) (C[binary_search(number)] +- 1).
теперь определим механизм движения указателей:
пока у нас последовательность на отрезке [l; r] "плохая", r++, берём A[r], если бинпоиском находим его в B, увеличиваем соответствующий элемент в C;
пока у нас последовательность на отрезке [l; r] "хорошая", релаксируем размер последовательности, уменьшаем что надо в C, l++;
итого асимптотика 2*N*M*log(N) (два прохода по A, проверка на "хорошесть", бинпоиск).

вроде ничего не забыл :-)
...
Рейтинг: 0 / 0
13.06.2011, 05:34
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306222
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

Да что ты. Злюсь я падругому
аж искры летят.
Чтож спасибо. Чесно нихрена
не врубил. Надо поспать.
...
Рейтинг: 0 / 0
13.06.2011, 05:46
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306273
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreymx
Участник
первоначальную последовательность A пропарсить
оставив только те, которые есть в B, и выбросив двойные, которые подряд
каждому оставшему числу прописать в характеристиках количество выброшенных, а также первую и последнюю позицию текущего числа в оригинальной A.
...
Рейтинг: 0 / 0
13.06.2011, 10:24
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306274
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreymx
Участник
andreymxпервоначальную последовательность A пропарсить
оставив только те, которые есть в B, и выбросив двойные, которые подряд
каждому оставшему числу прописать в характеристиках количество выброшенных, а также первую и последнюю позицию текущего числа в оригинальной A.хотя для случая
a = (2,5,2,5,2,5,2,5,2,3)
b=(2,5,3)
это ни хрена не поможет
:)
...
Рейтинг: 0 / 0
13.06.2011, 10:26
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306437
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
Все-таки допилил я свое корявое решение
ну такой я уж человек. Не могу без показухи.

Код: plaintext
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.
 public static int GetPositionLeastSequence(int[] A, int[] B)
        {
            int[] check = new int[B.Length];

            int countChecked = 0;
            
            int length = A.Length;
            int position = 0;

            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    if (A[i] == B[j])
                    {
                        if(A[check[j]] != A[i] || i == 0)
                        countChecked++;

                        check[j] = i;

                        if (countChecked >= B.Length)
                        {
                            if (check[j] - check.Min() < length)
                            {
                                position = check.Min();
                                length = check[j] - check.Min();
                            }
                        }
                    }
                }
            }

           return position;

        }
...
Рейтинг: 0 / 0
13.06.2011, 13:40
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306463
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если предположить что атомы в списке - это chars то можно
искать группы через Patterns.

Код: plaintext
1.
2.
3.
String A="1,2,3,4,5,3,2,4,8,5";
String B="5,2,3".replaceAll(",","");
Pattern pattern1=Pattern.compile(...+B+....);
....
...
Рейтинг: 0 / 0
13.06.2011, 14:03
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306589
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
Вот те на,

вы вообще запускали свою программу на различных тестах? ><
...
Рейтинг: 0 / 0
13.06.2011, 15:22
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306599
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
mayton,

увы, перестановки через регулярки эффективно никак не задать.
...
Рейтинг: 0 / 0
13.06.2011, 15:27
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306604
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

И так и сяк вертел.
В чем проблема?
...
Рейтинг: 0 / 0
13.06.2011, 15:29
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306613
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
А вообще, из каких условий вообще-то исходим?
А если B будет содержать несколько одинаковых значений?
А насколько вообще могут быть велики используемые значения?
Это я к тому, что нарисовался у меня некий алгоритм, но хочется уточнить...
...
Рейтинг: 0 / 0
13.06.2011, 15:36
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306614
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В моей постановке не должно быть перестановок. Есть поиск
подстрок состоящих из заданного множества символов.
...
Рейтинг: 0 / 0
13.06.2011, 15:37
| Ответить | Цитировать | Написать  
25 сообщений из 45, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=37306211&tid=1342882]:
 0ms
get settings:
 6ms
get forum list:
 18ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 150ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 44ms
get tp. blocked users:
 1ms
others: 208ms
total:  444ms
созд. / загр.: 444ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]