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

Код: 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, 03:37
    #37306208
Вот те на
Вот те на
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
Извини чувак чета я там намудрил.
Код: 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:47
    #37306211
dubov1994
dubov1994
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
неверно и неэффективно.

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

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

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

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

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

общий глупый алгоритм, поскольку об ограничениях топикстартер умолчал.
пусть 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:46
    #37306222
Вот те на
Вот те на
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
dubov1994,

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

Код: 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, 14:03
    #37306463
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
Если предположить что атомы в списке - это 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, 15:22
    #37306589
dubov1994
dubov1994
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
Вот те на,

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

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

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


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