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
|
|
|
Ну, и чо? На 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
|
|
|
Еще бы перл уметь курить, но идею я уловил.
Псиб всем откликнувшимся, буду писать
|
|
Storm_Trooper
|
Имперский штурмовик
|
|
|
|
Рег.: 11.03.2008
|
Сообщений: 66
|
Из: Корусант
|
Рейтинг: 71
|
|
Re: Помогите плиз алгорит придумать =)
[re: Zoobastik]
25.03.2008 11:40
|
|
|
|
blind
|
still alive
|
|
|
|
Рег.: 16.01.2004
|
Сообщений: 23129
|
Из: Хамовники
|
Рейтинг: 16483
|
|
Re: Помогите плиз алгорит придумать =)
[re: Zoobastik]
25.03.2008 11:54
|
|
|
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
|
|
|
за синтаксис этой поделки аффтаров нужно расстреливать. Особенно "приятно" смотреть на двустрочные функции в этих уродливых скобках. ЗЫ верный путь к окулисту
|
|
Storm_Trooper
|
Имперский штурмовик
|
|
|
|
Рег.: 11.03.2008
|
Сообщений: 66
|
Из: Корусант
|
Рейтинг: 71
|
|
Re: Помогите плиз алгорит придумать =)
[re: blind]
25.03.2008 14:43
|
|
|
как всегда, функциональное решение самое короткое
|
|
DizzyDen
|
достаточно добр
|
|
|
|
Рег.: 04.03.2003
|
Сообщений: 51430
|
Из: http://лакалхвост
|
Рейтинг: 13545
|
|
Re: Помогите плиз алгорит придумать =)
[re: Zoobastik]
25.03.2008 15:23
|
|
|
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
|
|
|
только вот писать это все надо без рекурсии задача стандартная на лексикографический перебор вариантов
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
|
|
|
mGauss [] должно быть [[]] по идее (и проверка типов эту ошибку пропустит). Тогда и случай mGauss [x] не придется рассматривать особо.
Но вообще это не тру хаскелл - слишком просто и не понятно, причем здесь теория категорий
code: f:: [[a]]->[[a]]
f=foldr (flip $ (flip (>>=)).(flip $ map.(:))) [[]]
|
|