Перебор комбинаций

[KobolD]

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

Задача собственно в следующем: Есть ящик в который можно положить инструменты, Молоток, Пила, Отвертка, Дрель и т.д. (пусть будет 10 инструментов). Так вот я могу положить все инструменты, а могу положить только отвертку и молоток или пилу, дрель и отвертку.
Последовательность укладки роли не играет молоток+пила и пила+молоток это одно и тоже.

Язык програмирования роли не играет но желательно на C#. В принципе можно просто словами алгоритм описать.

[evg_m]

упорядоченный список пила, отвертка, дрель, ...., молоток, рубанок, НИЧЕГО.

цикл ящик 1 от пила до НИЧЕГО
  цикл ящик 2 от ящик1 до НИЧЕГО
...
     цикл ящик N  от ящикN-1 до НИЧЕГО  
....  
         цикл ящик 10 от ящик9 до НИЧЕГО  
              если предметы разные то ХОРОШИЙ набор иначе ПЛОХОЙ набор

(при сравнении учитывать что два НИЧЕГО это РАЗНЫЕ предметы)

[KobolD]

Что то я не понял решение, можно коментарии какие-нибудь. Вопервых откуда взялось так много ящиков?
На входе есть массив:
string[] Instruments = { "Пила", "Молоток", "Отвертка", "Дрель", "Лобзик" };
И где то в цикле должен образовываться временный масив
{ "Пила", "Молоток" }, потом { "Пила", "Отвертка"}, ..... { "Пила", "Молоток", "Отвертка"}

[Zer0]

я могу помочь, но ближе к вечеру, есть готовый алгоритм генерации всех подмножеств массива (что по сути и нужно), но на Delphi, при желании могу словесно описать

если что пиши -392459949

[Vago]

Сообщение от KobolD

В принципе можно просто словами алгоритм описать.

Хранить все доселе найденные перестановки разрешается?

[evg_m]

1.

упорядоченный список пила, отвертка, дрель, ...., молоток, рубанок, НИЧЕГО.

добавляем к списку еще один элемент НИЧЕГО (причем он должен быть строго последним)

2.

цикл ящик 1 от пила до НИЧЕГО
  цикл ящик 2 от ящик1 до НИЧЕГО
...
     цикл ящик N  от ящикN-1 до НИЧЕГО  
....  
         цикл ящик 10 от ящик9 до НИЧЕГО

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

3.

если предметы разные то ХОРОШИЙ набор иначе ПЛОХОЙ набор

(при сравнении учитывать что два НИЧЕГО это РАЗНЫЕ предметы)

"восстанавливаем" исходное правило. Исключаем повторы предметов (пила, пила)


P.S. можно избавиться от проверки повторов

упорядоченный список пила, отвертка, дрель, ...., молоток, рубанок, НИЧЕГО1 НИЧЕГО2, .... , НИЧЕГО10(по числу ящиков).

след(элт) эдемент списка следующий за элт

цикл ящик 1 от пила до НИЧЕГО1
  цикл ящик 2 от след(ящик1) до НИЧЕГО2
...
     цикл ящик N  от след(ящикN-1) до НИЧЕГОN
....  
         цикл ящик 10 от след(ящик9) до НИЧЕГО10
            БЕРЕМ ГОТОВЫЙ НАБОР(ящик1, ящик2, ... ящик10)

и удаляем оттуда НИЧЕГО1, ... НИЧЕГО10.

[KobolD]

evg_m
Спасибо, теперь я разобрался. Только к сожалению меня такое решение не устраивает, т.к. количество циклов привязано к количеству инструментов, и если его менять то получается надо переписывать программу. Я так понимаю тут рекурсию надо использовать, буду сидеть разбираться.

Сообщение от Vago

Хранить все доселе найденные перестановки разрешается?

Да, так как из число относительно невелико (я думаю до ста миллионов меня устроит)

[Vago]

Это - "некрасивый" вариант (хотя и работающий). С хранением всего, что нагенерировали, и с проверкой "А было-ли уже?"

#!/usr/bin/python
# -*- coding: cp1251 -*-

x = ['Hammer', 'Saw', 'Screwdriver']
xAll = []
xAll.append( x )


def WasAlreadyGenerated( x ):
   for i in range( 0, len(xAll) ):
      if xAll[i] == x:
         return True

   return False


def Cnm( a ):
   if len( a ) == 1:                  # Уже нечего отбрасывать
      if not WasAlreadyGenerated( a ):    # Такой перестановки ещё не было?..
         xAll.append( a )             # ..Добавляем
   else:
#     Будем пытаться удалять по одному элементу
      for k in range( 0, len(a) ):
#        В силу специфики передачи параметров в Питоне, создаём локальную копию
         _a = []
         for j in range( 0, len(a) ):
            _a.append( a[j] )

         _a.remove( a[k] )	         # Удаляем k-й эл-т
         if not WasAlreadyGenerated( _a ):	 # Такой перестановки ещё не было?..
            xAll.append( _a )            # ..Добавляем

         Cnm( _a )

   return


def main():
   Cnm( x )
   for i in range( 0, len(xAll) ):
      print xAll[i]


main()

110314.jpg

Далi буде...

[Vago]

Без накопления.

#!/usr/bin/python
# -*- coding: cp1251 -*-

# x = ['Hammer', 'Saw', 'Screwdriver']
x = ['1', '2', '3', '4']

def Cnm( a ):
   kAlowestInX = x.index( a[len(a)-1] )
#  Local copy
   _a = []
   for j in range( 0, len(a) ):
      _a.append( a[j] )

   print a
   if len(a) == 1 and a[len(a)-1] == x[len(x)-1]:	# ВСЁ!
      return

   if a[len(a)-1] == x[len(x)-1]:	   # Достигли предела в "младшем разряде"
      _a.remove( _a[len(_a)-1] )     # Удаляем "крайний правый" элемент...
      _a.remove( _a[len(_a)-1] )     # ...и ещё раз...
      kAlowestInX = x.index( a[len(a)-2] )

   _a.append( x[kAlowestInX+1] )    # Добавляем ещё один эл-т в множество

   Cnm( _a )


def main():
   a = []
   a.append( x[0] )
   Cnm( a )


main()

[KobolD]

Спасибо Vago. Я решил остановиться на варианте перебора по маске.

        static string[] Instruments = { "1", "2", "3", "4"};
        static void Main(string[] args)
        {
            List<string> CurentState = new List<string>();
            bool[] Maska = new bool[Instruments.Length];
            while (Sdvig(ref Maska))
            {
                for (int i = 0; i < Maska.Length; i++)
                    if (Maska[i])
                        CurentState.Add(Instruments[i]);

                //Вот сдесь можно забирать текущий набор значений из списка CurentState

                for (int i = 0; i < CurentState.Count; i++)
                    Console.Write(CurentState[i].ToString());
                Console.WriteLine();
                CurentState.Clear();
            }
            Console.ReadLine();
        }

       
        static bool Sdvig(ref bool[] Mask)//Процедура выполняет побитовое увеличение на единичку
        {
            bool CF = true;
            for (int i = 0; i < Mask.Length; i++)
            {
                if ((CF) && (Mask[Mask.Length - 1]) && (i == Mask.Length - 1))//достигнут конец перебора (все единицы)
                    return false;
                if (CF)
                {
                    Mask[i] = !Mask[i];
                    if (Mask[i])
                        return true;
                }

            }
            return true;
        }