Помогите плиз алгорит придумать =)

0000

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

slonishka

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

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

artimon

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

Helga87

Ну, и чо? На C# это бы выглядело примерно так:



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>.

Maurog

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



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: соптимайзил чуток

0000

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

0000

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

artimon

$ 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

0000

Еще бы перл уметь курить, но идею я уловил.
Псиб всем откликнувшимся, буду писать

cyberrod

энто пыхпых

vall

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, [''])

cyberrod

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

cyberrod

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

apl13

mGauss :: [[a]] -> [[a]]

mGauss [] = []

mGauss [x] = [[ksi]|ksi <- x]

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

Dasar

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



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;

}

0000

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

kruzer25

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

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

0000

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

iakobi91

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

Dmitriy82

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

f:: [[a]]->[[a]]

f=foldr (flip $ (flip (>>.(flip $ map.( [[]]

0000

Чую меня камнями побьют, но это для подъема рейта в поисковиках (на формах гадить).

klyv

а вот это следовало тихо не упоминать

apl13

mGauss [] должно быть [[]] по идее

Э-э-э. А мне кажется как раз наоборот: пустое множество пустое же порождает.

f=foldr (flip $ (flip (>>.(flip $ map.( [[]]

Хотелось написать вариант, в котором нет ни одного слова map. ^_^

Dmitriy82

Длина входного списка определяет длину каждого элемента искомого списка. Кроме того, каждый элемент искомого списка сам является списком, каждый элемент которого должен входить в соответствующий элемент входного списка.
В случае []: длина входного списка 0, поэтому ответ - это список списков нулевой длины. Входит ли в него единственный список нулевой длины? Да, потому что каждый его элемент входит в соответствующий элемент входного списка (по крайней мере, нельзя утверждать обратного).
Другими словами, у нас ведь количество комбинаций есть произведение количеств вариантов по каждой позиции. Произведение нуля сомножетелей по соглашению (и не без оснований) считают равным нейтральному элементу по умножению, то есть единице. Поэтому в ответе должна быть одна комбинация (пустая).
И повторю уже приведённый аргумент: такое определение получается менее симметричным, избыточным и противоречивым (в том смысле что можно придумать естественные свойства этой функции, которые нарушатся в граничном случае т.к. приходится отдельно рассматривать вариант [x]. Если не нравится f [] = [[]], то выходом могло бы быть определение частичной функции, начиная с одноэлементного списка.
> Хотелось написать вариант, в котором нет ни одного слова map. ^_^
А мне хотелось написать вариант в котором ни одного шаблона.

apl13

Произведение нуля сомножетелей по соглашению (и не без оснований) считают равным нейтральному элементу по умножению, то есть единице.

Во как!

pitrik2

Во как!

стандартная вещь
ничего удивительного

Andbar

Вспомнилась эта статья:
http://www.insidepro.com/doc/003r.shtml
(всю тему не читал)

Оставить комментарий