Алгоритмы по комбинаторики...

[Марк]

Есть массив из 8 элементов, необходимо вывести все возможные варианты комбинаций множеств этих элементов (т.е. все возможные комбинации с одним элементом, затем с двумя и т.д.).
Какие-то идеи реализации задачи подскажите?

[Capella]

Это стандартный алгоритм с двойными for-скобками... Вы в каком языке программируете? Я Вам сейчас сделаю пример в Java (OOP), а Вы уже перекуёти мечи на оралы.

Добавлено спустя 9 минут 14 секунд:

{ for (int i  = 0; i < 8; i++)
             { for (int j = 0; j <= i; j++)
        System.out.println(p(i,j)); 
             }
          } 

Эо двойная скобка по двум переменным, теперь делаем р.

static long p(int n, int k)
            {return f(n)/f(n-k);
            }

это функция, теперь осталось спрограммировать только факультет:

 static long f(int n)
             { long f =1;
               while (n > 1) //определяем, что больше единицы
               f *= n--; //делает умножение и одновременно понижает n на единичку, таким    образом получаем факультет.
               return f;
             }

[Марк]

Capella писал(а):

Это стандартный алгоритм с двойными for-скобками... Вы в каком языке программируете? Я Вам сейчас сделаю пример в Java (OOP), а Вы уже перекуёти мечи на оралы.

Добавлено спустя 9 минут 14 секунд:

{ for (int i  = 0; i < 8; i++)
             { for (int j = 0; j <= i; j++)
        System.out.println(p(i,j)); 
             }
          } 

Эо двойная скобка по двум переменным, теперь делаем р.

static long p(int n, int k)
            {return f(n)/f(n-k);
            }

это функция, теперь осталось спрограммировать только факультет:

 static long f(int n)
             { long f =1;
               while (n > 1) //определяем, что больше единицы
               f *= n--; //делает умножение и одновременно понижает n на единичку, таким    образом получаем факультет.
               return f;
             }

И тут меня нашли

Прогамирую на С++ (ООП прилогается)...
На вскидку вроде все ясно... более подробно разберу позже... а то завтра еще не ленты

[e2e4]

Простите, не могли бы вы пояснить суть понятия "факультет"?
Я так понял, что p(i,j) возвращает только номер элемента массива?

[Capella]

e2e4

Нет, она не возвращает просто номера массива. $p$ это метода, которое даёт назад одно число. Она имеет два параметра (оба integer) и считает деленеи функции $f$ от этих двух параметров. в данном случае параметр $n$ будет инициализован параметром $j$, который я определила доходящим до 8, а параметр $k$ будет соотвествовать $i$ (более правильно сказать, что i соотвествует k ). После этого, получаем просто какую-то формулу, которая даёт вот такую штуку: $p = \frac a {a-b}$. В данном случае $a$ и $b$ функции факультета, поэтому я пишу 3-ию методу, уже задающую сам факультет. Дело в том, что в библиотеки Java такой функции нет (по крайней мере в старых версиях, которые я проходила) и определяю её сама. В Java значок "!" например вот так $8! = 8 \cdot 7!$ означает $ 8 \ne 8 \cdot 7 $. А уже сам факультет: я определяю какую-то константу равную 1 и начинаю умножать на неё все члены n, понижая их каждый раз на 1. В этом и есть суть факультета.

[Марк]

Марк писал(а):

На вскидку вроде все ясно... более подробно разберу позже...

вообщемто на С, код выглидит также, только ответ выходит
1-1-1-1-2-2-1-3-6-6-1-4-12-24-24-1-5-20-60-120-120-1-6-30-120-360-720-720-1-7-42-210-840-2520-5040-5040
Я представлял его так:
1-2-3-4-5-6-7-8-12-13-...-18-21-23-...-28-31-32-34-... ну т.д.

[Capella]

Хм, сейчас я посмотрю на Eclipse, а пока такой вопрос: Вы p и f внутри внушних фигурных скобок сделали? Я ожидаю совсем другой аутпут...

[Марк]

Capella писал(а):

Хм, сейчас я посмотрю на Eclipse, а пока такой вопрос: Вы p и f внутри внушних фигурных скобок сделали? Я ожидаю совсем другой аутпут...

http://f1gnya.narod.ru/komb.txt - вот весь листинг...

[Capella]

Ну алгоритм по меньшей мере выглядит не плохо, насчёт самого синтакса не скажу, потому что в "С++" не пргораммирую... Но я думаю, что если компилирует, то ок..

Добавлено спустя 1 час 27 минут 53 секунды:

Я поняла, что Вас беспокоит. То, что вы получаете - так и дожно быть, Вы получили просто пермутацию, а ведь Вы не суммируете ещё все Ваши результаты. Другими словами вы сейчас получили просто числовое решение, а в "Математике" я написала вам $\sum\limits_{n=1}^8 \frac {8!} {(8-n)!}$ Теперь Вам надо сделать сумму. Воспользуйтесь библиотекой С++ и посмотрите в классе MATH (или аналогичном) методу, которая суммирует по индексу (или что-то такое). В Java это sum(); по моему.
И ещё по поводу кода: for-скобка для $i$ не нужна, возьмите постоянное значение на том-же месте в коде:

 int i = 8; 

[Марк]

И правда, работает, только:

for (int j = 0; j <= i; j++)

надо поменять на

for (int j = 0; j < i; j++)

- разница в знаке <...
Только это не совсем то, что я хотел... мне надо не количество элементов, а сами элементы (все 69281 элементов)

[Capella]

Насчёт "равно" Вы не правы, эта часть кода правильная, единственное, что ещё логично сделать, это стартовать значение $j = 1$, т.е. с одного вытянутого шарика, а не с 0 вытянутых (хотя теоретичеси это тоже вариант). Вот Вам правильная версия кода:

 { int i = 8;
              {for (int j = 1; j <= i, j++) ... } }

Теперь я получила такой output:

8 56 336 1680 6720 20160 40320 40320

Здесь не совсем стало понятно, что Вам надо делать. Я так думала, что программа должна считать эти самые 109600 и выдавать это число (мы собственно и движемся в этом направлении и осталось уже немного), но теперь Вы хотите например, чтобы выдавались сами кубики? (т.е. каждому кубику присваивался номер и показывались все 109600 комбинаций? ) Ваш ответ, кстати, 69281 не правилен, должно быть восемь суммандов от 1 до 8 вытянутых кубиков включительно, а у Вас до 7 вытянутых, но это из=за того, что Вы убрали равно.... (по крайней мере, так Вы спрашивали раньше)

[незваный гость]

Марк писал(а):

Есть массив из 8 элементов, необходимо вывести все возможные варианты комбинаций множеств этих элементов (т.е. все возможные комбинации с одним элементом, затем с двумя и т.д.).
Какие-то идеи реализации задачи подскажите?

Вам нужны подмножества, или их число (как-то сгруппированное)?
Если число, то ответ $256 = 2^8$ (включая пустое множество).

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

e2e4 писал(а):

Простите, не могли бы вы пояснить суть понятия "факультет"?

Это факториал. Очевидно, что p(n, k) возвращает $\frac{n!}{k!}$.

Я по-прежнему в недоумении, какое это имеет отношение к задаче…

Напишу решение на Python, чтобы было нужно разобраться, что происходит:

def subsets(used, selected):
  if used < len(raw):
    subsets(used + 1, selected)
    acc[selected] = raw[used]
    subsets(used + 1, selected + 1)
  else:
    print acc[:selected]

if __name__ == "__main__":
  raw = range(8)
  acc = [None] * len(raw)
  subsets(0, 0)

~~~~~~~~~~~~~~~~~~~~
Есть еще один вариант, более хулиганский. Для маленького массива, порядка восьми элементов, он проходит, но для больших может не хватить размерности целого. Впрочем, в этом случае и выводить слишком долго. Идея алгоритма — просто перебирать все целые числа и использовать из как битовую маску.

def subsets(raw):
  acc = [None] * len(raw)
  for bitmask in range(2**len(raw)):
    k = 0
    for j in range(len(raw)):
      if bitmask & (1 << j):
        acc[k] = raw[j]
        k += 1
    print acc[:k]

if __name__ == "__main__":
  raw = range(8)
  subsets(raw)

Обратите внимание: в этом случае нам acc фактически не нужен. Затратив чуть больше усилий на программирование, мы можем непосредственно печатать ответ.

[Марк]

def subsets(used, selected):

def - это что? subsets - функция решения задачи?
range() - считает число элементов?

[Capella]

Если ваш алгоритм должен просто давать варианты перестановок всех кубиков, то алгоритм не должен быть там каким-то сложным... Во первых факультет Вам, как отметил уже незваный гость, действительно ни к чему. Я-бы сама сделала: определила объект класса Vector начала наполнять его числами, примерно так:

 Vector v = new Vector();

for( int i = 1, i <= 87654321, i ++)
 {v.addElement();}
   return v; 

Там-бы были все числа от 1 до 87654321. потом надо просто сделать while-скобку с условием, что ни один элемент вектора не равен 9 и нету равных элементво внутри вектора (или array) $a$ ( $a$ будет определять длину и количество знаков в каждом элементе ). Для этого можно определить какую-нибудь методу, которая звучала-бы примерно так:

 boolean p() {
 {for (int i = 0; i < a.length; i++)
   {for (int k = 0; k < i; k++)
        if( a[i] != 9 ¦¦ a[i] != a[k] ) {
           return true;}
   }
  }  

Примерно такой псеудокод Эта метода быдет вызываться в while-скобке и если значение true, то будет возвращаться число, стоящее на i-ом месте в векторе $v$.

Вот такая идея (немного подправила код, дав разные названия и исправив длину в for-скобке)

[Werwolf]

Что-то лично мне из предложенного больше всего импонирует рекурсия. В качестве примера

#include <iostream.h>

const int N=8;

void recur(int k, int i, bool used[N], int list[N]) {
   if (k==0) {
      for (int j=i-1; j>=0; j--) 
         cout<<list[j];
      cout<<endl;
   }
   else {
      for (int j=0; j<N; j++)
         if (!used[j]) {
            used[j]=true;
            list[k-1]=j+1;
            recur(k-1,i,used,list);
            used[j]=false;
         };
   };
};

int main() {
   bool used[N];
   for (int j=0; j<N; j++) used[j]=false;
   int list[N];
   int a;
   for (j=1; j<=N; j++) {
      recur(j,j,used,list);
//      cin>>a; //uncomment this string to get delays
   };
   return 0;
};