Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.snto-msu.net/showflat.php?Number=7352840&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 14:19:45 2016
Кодировка: Windows-1251
Помогите плиз алгорит придумать =) - Public forum of MSU united student networks
Root | Google | Yandex | Mail.ru | Kommersant | Afisha | LAN Support
  
Technical >> Development (Archive)

Страницы: 0 | 20 | показать все | след. страница
Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Помогите плиз алгорит придумать =)
      25.03.2008 11:03
 

Попросили программку написать, а вот алгоритм реализации одного куска не получается придумать.
Собственно вот что нужно:
{A|B|C}, {C|D|E|F}, {G|H}, ...
Надо нагенерить все возможные наборы вида
A, C, G, ...
B, C, H, ...

Сложность в том, что {...|...} может быть сколько угодно, ну и в каждой такой штуке A, B, C-элементов то же.
Пишется все на C++, данные хранятся в массиве Data[Номер {...|...}] [Номер буквы], но это не важно, т.к. можно переписать.


Bachan
god's pee

Рег.: 26.10.2002
Сообщений: 37551
Рейтинг: 5335
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:08
 

Quote:

Сложность в том, что {...|...} может быть сколько угодно



неужели прям совсем сколько угодно? двадцать пять тыщ мильенов может быть? ))



я АЭС фачил в эсс!
Lynn
'Кофеман'

Рег.: 28.02.2003
Сообщений: 7316
Из: Тропарево-Никулино
Рейтинг: 905
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:12
 

И что, рекурсия не канает?



Плыл в небе, глубоком как сон,
Кокаиновый пес
- Адриан и Александр
Krasin

Рег.: 23.06.2004
Сообщений: 7039
Из: Калифорния
Рейтинг: 3386
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:18
1

Ну, и чо? На C# это бы выглядело примерно так:
code:
void GenerateVariants(int depth, List<string> variants, char[] current, List<string> result) { if (depth >= variants.Count) { result.Add(new String(current)); } for (int i = 0; i < variants[depth].Length; i++) { current[depth] = variants[depth][i]; GenerateVariants(depth+1, variants, current, result); } }


В случае С++, вместо List<string> надо будет использовать vector<string>.



Редактировал Krasin (25.03.2008 11:40)
horror
гонобобель

Рег.: 30.09.2002
Сообщений: 3784
Рейтинг: 2137
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:19
 

попробую объяснить свой подход.
пусть таких скобочек N штук.
делаем массив
int CurrentLetter[N] (инициализируем нулями)
int Limits[N]; (Limits[k] = кол-во буковок в скобочке номер k минус 1)

Метакод:
code:
main() { //цикл, пока массивы не совпадут while (1) { PrintSet(CurrentLetters, N); int i; for (i = 0; i < N; i++) { if (!IncrementNumber(CurrentLetters + i, Limits + i)) break; } if (i == N) break; } } bool IncrementNumber(int* current, int* limit) { (*current)++; if (*current > *limit) { *current = 0; return true; } return false; } void PrintSet(int* current, int size) { for(int i=0; i < size; i++) { std::cout << Data[i][current[i]] << "," } std::cout << std::endl; }


ps: соптимайзил чуток



Редактировал horror (25.03.2008 11:29)
Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:20
 

На вход будет подаваться строка вида {A|B|C} {E|D} {G|H}
Скобочек {} ну штук 10, каждых элементов то же 10 макс, т.е. на скорость алгоритма пофиг.
Для входной строки ответ должен быть вот таким
AEG
AEH
ADG
ADH
BEG
BEH
BDG
BDH
CEG
CEH
CDG
CDH

Рекурсию, что то не соображу как :(
 

Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Re: Помогите плиз алгорит придумать =) [re: Krasin]
      25.03.2008 11:22
 

О, попробую перевести :)

Lynn
'Кофеман'

Рег.: 28.02.2003
Сообщений: 7316
Из: Тропарево-Никулино
Рейтинг: 905
  Re: Помогите плиз алгорит придумать =) [re: Lynn]
      25.03.2008 11:25
 

code:
$ cat a.php <?php $x = array( array(1, 2, 3), array('a', 'b', 'c'), array('X', 'Y'), ); function go($x, $n = 0, $res = array()) { if ($n == count($x)) { echo implode(',', $res), "\n"; return; } foreach ($x[$n] as $v) { array_push($res, $v); go($x, $n + 1, $res); array_pop($res); } } go($x); ?> $ php a.php 1,a,X 1,a,Y 1,b,X 1,b,Y 1,c,X 1,c,Y 2,a,X 2,a,Y 2,b,X 2,b,Y 2,c,X 2,c,Y 3,a,X 3,a,Y 3,b,X 3,b,Y 3,c,X 3,c,Y




Плыл в небе, глубоком как сон,
Кокаиновый пес
- Адриан и Александр
Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Re: Помогите плиз алгорит придумать =) [re: Lynn]
      25.03.2008 11:38
 

:D
Еще бы перл уметь курить, но идею я уловил.

Псиб всем откликнувшимся, буду писать :)

Storm_Trooper
Имперский штурмовик

Рег.: 11.03.2008
Сообщений: 66
Из: Корусант
Рейтинг: 71
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:40
4

энто пыхпых

blind
still alive

Рег.: 16.01.2004
Сообщений: 23129
Из: Хамовники
Рейтинг: 16483
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 11:54
5

def l(a):
return [x + y for x in a[0] for y in l(a[1:])] if a else ['']


о, еще круче придумал! без всякой рекурсии.

a = ['ABC', 'CDEF', 'GH']
print reduce(lambda l, s: [x + y for x in l for y in s], a, [''])



13/37 =)
Storm_Trooper
Имперский штурмовик

Рег.: 11.03.2008
Сообщений: 66
Из: Корусант
Рейтинг: 71
  Re: Помогите плиз алгорит придумать =) [re: Krasin]
      25.03.2008 14:39
2

за синтаксис этой поделки аффтаров нужно расстреливать. Особенно "приятно" смотреть на двустрочные функции в этих уродливых скобках.
ЗЫ верный путь к окулисту

Storm_Trooper
Имперский штурмовик

Рег.: 11.03.2008
Сообщений: 66
Из: Корусант
Рейтинг: 71
  Re: Помогите плиз алгорит придумать =) [re: blind]
      25.03.2008 14:43
3

как всегда, функциональное решение самое короткое

DizzyDen
достаточно добр

Рег.: 04.03.2003
Сообщений: 51430
Из: http://лакалхвост
Рейтинг: 13545
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 15:23
3

code:
mGauss :: [[a]] -> [[a]] mGauss [] = [] mGauss [x] = [[ksi]|ksi <- x] mGauss (x:s) = [ksi:y|y <- mGauss s, ksi <- x]




If stateless paradigm is good for your code, why shouldn't it be for your country?
DarkGrayМодератор
Carpal Tunnel

Рег.: 30.09.2002
Сообщений: 31421
Рейтинг: 8956
  Re: Помогите плиз алгорит придумать =) [re: Krasin]
      25.03.2008 15:47
3

только вот писать это все надо без рекурсии
задача стандартная на лексикографический перебор вариантов

variants - это какое кол-во букв может быть на каждом месте
code:
int[] Init(int[] variants) { return new int[variants.Length]; } //true - есть еще один вариант, false - перебор окончен bool Next(int[] variant, int[] variants) { for(int i = variant.Length-1; i>=0; --i) { variant[i]++; if (variant[i] < variants[i]) return true; variant[i] = 0; } return false; }


Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 15:52
 

Спасибо всем =)
Все сделал.

penartur2

Рег.: 16.06.2005
Сообщений: 54495
Рейтинг: 429
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 20:11
 

В ответ на:

Скобочек {} ну штук 10, каждых элементов то же 10 макс, т.е. на скорость алгоритма пофиг.



У тебя там 10^10 вариантов выйдет, а у современных процессоров такого же порядка количество операций в секунду.
Неужели тебе ну совсем пофигу, будет оно выполняться пять секунд или пять часов?



Я ушел на новый форум.
Там правовое государство. А еще можно удобно листать аплоад ;)
Zoobastik
Комок меха

Рег.: 18.10.2003
Сообщений: 7462
Из: За спиной
Рейтинг: 4345
  Re: Помогите плиз алгорит придумать =) [re: penartur2]
      25.03.2008 21:19
 

Пофиг, это небольшая тулза для знакомого.

pipiska
як цуп цоп

Рег.: 09.06.2004
Сообщений: 3458
Рейтинг: 696
  Re: Помогите плиз алгорит придумать =) [re: Zoobastik]
      25.03.2008 22:02
 

кроссворды разгадывает?

Vlad
addict

Рег.: 18.09.2004
Сообщений: 446
Рейтинг: 236
  Re: Помогите плиз алгорит придумать =) [re: DizzyDen]
      25.03.2008 22:13
5


 mGauss [] должно быть [[]] по идее (и проверка типов эту ошибку пропустит). Тогда и случай mGauss [x] не придется рассматривать особо.

Но вообще это не тру хаскелл - слишком просто и не понятно, причем здесь теория категорий :)
code:
f:: [[a]]->[[a]] f=foldr (flip $ (flip (>>=)).(flip $ map.(:))) [[]]



Страницы: 0 | 20 | показать все | след. страница

Technical >> Development (Archive)

Дополнительная информация
0 зарегистрированных и 1 анонимных пользователей просматривают этот форум.

Модераторы:  DarkGray 

Печать темы
>>
Права
      Вы можете создавать новые темы
      Вы можете отвечать на сообщения
      HTML отключен
      UBBCode включен

Рейтинг:
Просмотров темы:

Переход в