Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.11.2010, 13:14
Новичок

Отправить личное сообщение для lobovmaxim Посмотреть профиль Найти все сообщения от lobovmaxim
 
Регистрация: 28.11.2010
Сообщений: 6

Комбинации параметров
Доброго времени суток форумчане! Нужен алгоритм, который бы составил все возможные комбинации параметров (см. таблицу во вложении). Цифры в колонках param разные, повторятся не могут. Количество цифр в каждой колонке может разное. Количество параметров (колонок) тоже, но не более 7.

вариантов = Кол-во param1 * Кол-во param2 * Кол-во param3 *...*Кол-во paramn
Для это примера вариантов = 30

10, 21, 34
10, 21, 36
10, 21, 37
10, 21, 39
10, 21, 40

10, 23, 34
10, 23, 36
.....
15, 23, 40

Кто может, очень прошу помочь!
Изображения:
Тип файла: png 1.PNG (3.2 Кб, 19 просмотров)

Последний раз редактировалось lobovmaxim, 28.11.2010 в 13:19.
  #2  
Старый 28.11.2010, 14:03
гость

 
Сообщений: n/a

алгоритма здесь нет. просто тупо вложенными циклами перебираешь комбинации.

если параметров переменное число - заворачивай циклы в рекурсию. это strictly технический прием, т.к. обычно языки программирования не позволяют тебе иметь несколько вложеннх циклов переменного количества. с рекурсией у тебя каждый уровень вложенность будет отдельным рекурсивным вызовом. могу написать как сделать, если укажешь язык
  #3  
Старый 28.11.2010, 14:05
гость

 
Сообщений: n/a

ну еще, как вариант, переход к следующей комбинации можно рассмотреть как прибавление единицы к числу в системе счисления с переменными основаниями... но вложенными циклами проще.
  #4  
Старый 28.11.2010, 16:44
Новичок

Отправить личное сообщение для lobovmaxim Посмотреть профиль Найти все сообщения от lobovmaxim
 
Регистрация: 28.11.2010
Сообщений: 6

Язык php. Структура исходного массива выглядит так:

$params['pr_name1'] = array('values' => array(12, 16, 18, 20), 'field_name'=> 'param3');
$params['pr_name2'] = array('values' => array(11, 21, 23), 'field_name'=> 'param4');
$params['pr_name3'] = array('values' => array(32, 31), 'field_name'=> 'param5');

Пробовал просто циклами - нормально, но не могу сделать рекурсией чтобы работало.
  #5  
Старый 28.11.2010, 17:15
гость

 
Сообщений: n/a

на php не пишу. могу написать на с/c++, python, java/c#, go, pascal. что предпочитаете?
  #6  
Старый 28.11.2010, 17:23
гость

 
Сообщений: n/a

вот на питоне. надеюсь вас не затруднит самому перевести на пхп

Код:
user@magrathea:~$ cat ./z.py 
#!/usr/bin/env python

params = {}
params['pr_name1'] = { 'values': [12, 16, 18, 20], 'field_name': 'param3' }
params['pr_name2'] = { 'values': [11, 21, 23], 'field_name': 'param4' }
params['pr_name3'] = { 'values': [32, 31], 'field_name': 'param5' }

keys = params.keys()
combination = []

def recurse():
    k = len(combination)
    if k == len(keys):
        print ' '.join(combination)
    else:
        field_name = params[keys[k]]['field_name']

        for value in params[keys[k]]['values']:
            combination.append('%s=%s' % (field_name, value))
            recurse()
            combination.pop()

recurse()
user@magrathea:~$ ./z.py 
param3=12 param4=11 param5=32
param3=12 param4=11 param5=31
param3=12 param4=21 param5=32
param3=12 param4=21 param5=31
param3=12 param4=23 param5=32
param3=12 param4=23 param5=31
param3=16 param4=11 param5=32
param3=16 param4=11 param5=31
param3=16 param4=21 param5=32
param3=16 param4=21 param5=31
param3=16 param4=23 param5=32
param3=16 param4=23 param5=31
param3=18 param4=11 param5=32
param3=18 param4=11 param5=31
param3=18 param4=21 param5=32
param3=18 param4=21 param5=31
param3=18 param4=23 param5=32
param3=18 param4=23 param5=31
param3=20 param4=11 param5=32
param3=20 param4=11 param5=31
param3=20 param4=21 param5=32
param3=20 param4=21 param5=31
param3=20 param4=23 param5=32
param3=20 param4=23 param5=31
  #7  
Старый 28.11.2010, 17:27
Новичок

Отправить личное сообщение для lobovmaxim Посмотреть профиль Найти все сообщения от lobovmaxim
 
Регистрация: 28.11.2010
Сообщений: 6

Спасибо! Сейчас попробую.. )
  #8  
Старый 28.11.2010, 20:24
Новичок

Отправить личное сообщение для lobovmaxim Посмотреть профиль Найти все сообщения от lobovmaxim
 
Регистрация: 28.11.2010
Сообщений: 6

Вот на php. Еще раз спасибо!

$keys = array_keys($new_params);

$combination = array();
recurse($new_params, $keys, $combination);

function recurse($new_params, &$keys, &$combination){
$k = count($combination);

if($k == count($keys)){
print_r($combination);
}else{
$field_name = $new_params[$keys[$k]]['field_name'];

foreach($new_params[$keys[$k]]['values'] as $value){
$combination[$field_name] = $value;

recurse($new_params, $keys, $combination);
array_pop($combination);
}
}
}

Array ( [product_param3] => 12 [product_param4] => 11 [product_param5] => 32 )
Array ( [product_param3] => 12 [product_param4] => 11 [product_param5] => 31 )
Array ( [product_param3] => 12 [product_param4] => 21 [product_param5] => 32 )
Array ( [product_param3] => 12 [product_param4] => 21 [product_param5] => 31 )
Array ( [product_param3] => 12 [product_param4] => 23 [product_param5] => 32 )
Array ( [product_param3] => 12 [product_param4] => 23 [product_param5] => 31 )
Array ( [product_param3] => 16 [product_param4] => 11 [product_param5] => 32 )
Array ( [product_param3] => 16 [product_param4] => 11 [product_param5] => 31 )
Array ( [product_param3] => 16 [product_param4] => 21 [product_param5] => 32 )
Array ( [product_param3] => 16 [product_param4] => 21 [product_param5] => 31 )
Array ( [product_param3] => 16 [product_param4] => 23 [product_param5] => 32 )
Array ( [product_param3] => 16 [product_param4] => 23 [product_param5] => 31 )
Array ( [product_param3] => 18 [product_param4] => 11 [product_param5] => 32 )
Array ( [product_param3] => 18 [product_param4] => 11 [product_param5] => 31 )
Array ( [product_param3] => 18 [product_param4] => 21 [product_param5] => 32 )
Array ( [product_param3] => 18 [product_param4] => 21 [product_param5] => 31 )
Array ( [product_param3] => 18 [product_param4] => 23 [product_param5] => 32 )
Array ( [product_param3] => 18 [product_param4] => 23 [product_param5] => 31 )
Array ( [product_param3] => 20 [product_param4] => 11 [product_param5] => 32 )
Array ( [product_param3] => 20 [product_param4] => 11 [product_param5] => 31 )
Array ( [product_param3] => 20 [product_param4] => 21 [product_param5] => 32 )
Array ( [product_param3] => 20 [product_param4] => 21 [product_param5] => 31 )
Array ( [product_param3] => 20 [product_param4] => 23 [product_param5] => 32 )
Array ( [product_param3] => 20 [product_param4] => 23 [product_param5] => 31 )

Последний раз редактировалось lobovmaxim, 28.11.2010 в 20:27.
  #9  
Старый 28.11.2010, 21:52
Новичок

Отправить личное сообщение для lobovmaxim Посмотреть профиль Найти все сообщения от lobovmaxim
 
Регистрация: 28.11.2010
Сообщений: 6

Проблема теперь в следующем:
- Как сделать так чтобы функция recurse() вернула массив с этими комбинациями? Делаю вот так, но возвращает массив не совсем в том виде в котором нужно.
Код:
$keys = array_keys($new_params);
$combination = array();
$combinations = recurse($new_params, $keys, $combination);
  
foreach($combinations as $comb){
  print_r($comb);
  echo '<br />';
}

function recurse($new_params, $keys, &$combination){
  $k = count($combination);  
  if($k == count($keys)){    
    $comb = $combination;
  }else{
    $field_name = $new_params[$keys[$k]]['field_name'];

    foreach($new_params[$keys[$k]]['values'] as $value){
      $combination[$field_name] = $value;
      $comb[] = recurse($new_params, $keys, $combination);
      array_pop($combination);
    }
  } 
  return $comb;
}
Array ( [0] => Array ( [0] => Array ( [product_param3] => 12 [product_param4] => 11 [product_param5] => 32 ) [1] => Array ( [product_param3] => 12 [product_param4] => 11 [product_param5] => 31 ) ) [1] => Array ( [0] => Array ( [product_param3] => 12 [product_param4] => 21 [product_param5] => 32 ) [1] => Array ( [product_param3] => 12 [product_param4] => 21 [product_param5] => 31 ) ) [2] => Array ( [0] => Array ( [product_param3] => 12 [product_param4] => 23 [product_param5] => 32 ) [1] => Array ( [product_param3] => 12 [product_param4] => 23 [product_param5] => 31 ) ) )
Array ( [0] => Array ( [0] => Array ( [product_param3] => 16 [product_param4] => 11 [product_param5] => 32 ) [1] => Array ( [product_param3] => 16 [product_param4] => 11 [product_param5] => 31 ) ) [1] => Array ( [0] => Array ( [product_param3] => 16 [product_param4] => 21 [product_param5] => 32 ) [1] => Array ( [product_param3] => 16 [product_param4] => 21 [product_param5] => 31 ) ) [2] => Array ( [0] => Array ( [product_param3] => 16 [product_param4] => 23 [product_param5] => 32 ) [1] => Array ( [product_param3] => 16 [product_param4] => 23 [product_param5] => 31 ) ) )
Array ( [0] => Array ( [0] => Array ( [product_param3] => 18 [product_param4] => 11 [product_param5] => 32 ) [1] => Array ( [product_param3] => 18 [product_param4] => 11 [product_param5] => 31 ) ) [1] => Array ( [0] => Array ( [product_param3] => 18 [product_param4] => 21 [product_param5] => 32 ) [1] => Array ( [product_param3] => 18 [product_param4] => 21 [product_param5] => 31 ) ) [2] => Array ( [0] => Array ( [product_param3] => 18 [product_param4] => 23 [product_param5] => 32 ) [1] => Array ( [product_param3] => 18 [product_param4] => 23 [product_param5] => 31 ) ) )
Array ( [0] => Array ( [0] => Array ( [product_param3] => 20 [product_param4] => 11 [product_param5] => 32 ) [1] => Array ( [product_param3] => 20 [product_param4] => 11 [product_param5] => 31 ) ) [1] => Array ( [0] => Array ( [product_param3] => 20 [product_param4] => 21 [product_param5] => 32 ) [1] => Array ( [product_param3] => 20 [product_param4] => 21 [product_param5] => 31 ) ) [2] => Array ( [0] => Array ( [product_param3] => 20 [product_param4] => 23 [product_param5] => 32 ) [1] => Array ( [product_param3] => 20 [product_param4] => 23 [product_param5] => 31 ) ) )
  #10  
Старый 28.11.2010, 22:00
гость

 
Сообщений: n/a

recurse не должна никаких массивов возвращать. это будет слишком медленно.

передавайте ей по ссылке массив в котором вы хотите хранить результаты, и пусть она вместо print'а очередного результата будет в этот массив добавлять очередную комбинацию
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск неизвестных параметров геометрической фигуры по имеющимся гость Искусственный интеллект, нейронные сети 4 16.12.2009 14:44
все возможные комбинации знаков ... гость Математические алгоритмы 3 09.12.2009 20:43
Восстановление вектора входных параметров по выходному в нейронных сетях Geck Искусственный интеллект, нейронные сети 11 07.12.2009 02:34