2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Алгоритмы по комбинаторики...
Сообщение14.02.2007, 01:52 
Есть массив из 8 элементов, необходимо вывести все возможные варианты комбинаций множеств этих элементов (т.е. все возможные комбинации с одним элементом, затем с двумя и т.д.).
Какие-то идеи реализации задачи подскажите?

 
 
 
 
Сообщение14.02.2007, 02:12 
Аватара пользователя
Это стандартный алгоритм с двойными 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;
             }

 
 
 
 
Сообщение14.02.2007, 02:19 
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;
             }

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

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

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

 
 
 
 
Сообщение14.02.2007, 17:54 
Аватара пользователя
e2e4

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

 
 
 
 
Сообщение14.02.2007, 21:08 
Марк писал(а):
На вскидку вроде все ясно... более подробно разберу позже...

вообщемто на С, код выглидит также, только ответ выходит
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-... ну т.д.

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

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

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

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

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

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

Код:
int i = 8;

 
 
 
 
Сообщение15.02.2007, 02:22 
И правда, работает, только:
Код:
for (int j = 0; j <= i; j++)
надо поменять на
Код:
for (int j = 0; j < i; j++)
- разница в знаке <...
Только это не совсем то, что я хотел... мне надо не количество элементов, а сами элементы (все 69281 элементов) :twisted:

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

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


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

Код:
8 56 336 1680 6720 20160 40320 40320


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

 
 
 
 
Сообщение15.02.2007, 09:42 
Аватара пользователя
:evil:
Марк писал(а):
Есть массив из 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 фактически не нужен. Затратив чуть больше усилий на программирование, мы можем непосредственно печатать ответ.

 
 
 
 
Сообщение15.02.2007, 12:58 
Код:
def subsets(used, selected):

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

 
 
 
 
Сообщение15.02.2007, 13:26 
Аватара пользователя
Если ваш алгоритм должен просто давать варианты перестановок всех кубиков, то алгоритм не должен быть там каким-то сложным... Во первых факультет Вам, как отметил уже незваный гость, действительно ни к чему. Я-бы сама сделала: определила объект класса 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;}
   }
  } 


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

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

 
 
 
 
Сообщение15.02.2007, 19:20 
Что-то лично мне из предложенного больше всего импонирует рекурсия. В качестве примера
Код:
#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;
};

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group