помогите девушке в С++

[Н]

не могу написать программу в С++, формулирующую все предложения, которые можно составить из словосочетаний "ваши прекрасные глаза ", "сулят"," мне", " сметрть", "прекрасная маркиза", "от любви". Все возможные перестановки.

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

А программу, которая печатает все возможные перестановки 1,2,3,4,5,6 Вы написать можете? Это не риторический, а весьма практический вопрос.

[Н]

например перестановки чисел 123,
for (i=0, i<3, i++)
for (j=i+1, j<3, j++)
for (k=j+1, k<3,k++)
if (a[i]!=a[j]&&a[i]!=a[k])
cout <<a[i],,a[j]<<a[k];
так?

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

Вообще-то, нет. По трем причинам причинам:
1) Программа выдает единственную перестановку 1, 2, 3. Других не находит.
2) Метод плохо обобщается на большее количество чисел -- каждый раз надо программу переписывать заново. Написать же функцию, работающую для произвольной длины совсем тяжело. Можно, конечно, используя рекурсию, но все равно -- тяжело.
3) Эффектиность метода быстро падает. Доля перестановок ${\rm O}({\rm e}^{-n})$.

Один из более эффективных алгоритмов основан на том, что существует ровно $n!$ перестановок длины $n$. Заводим массив переставляемых элементов. На каждой итерации: переставляем по кругу $a[0]... a[k]$, где $k$ -- самое большой индекс, такой что $k!$ делит номер итерации. Кончаем крутить цикл после $n!$ итераций.

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

[Werwolf]

А почему рекурсией тяжело для произвольной длины?

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

Werwolf писал(а):

А почему рекурсией тяжело для произвольной длины?

Ну недолюбливаю я рекурсию. Не то чтобы боюсь или не использую, а так -- недолюбливаю. Считаю, что использование реурсии нуждается в обосновании.
1) Рекурсия имеет глубину, равную длине списка. Проверка на неповторимость получившегося объекта все равно остается квадратичной (можно изощряться со множествами, и, тогда, может быть, удастся уменьшить сложность проверки за счет увеличения сложности цикла.

2) Большинство известных мне систем программирования не имеют exception на переполнение стека. Это приводит к тому, что если стек переполняется, то или возникает системная ошибка и программа немедленно прекращается, или происходит порча данных (и лучше бы была системная ошибка). Я ни разу не видел программной обработки переполнения стека.

[Н]

кто-нибудь может написать по подробнее?

[Willow]

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

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

К примеру 255 элементов будут перечислять на моем компьютере $10^{495}$ лет, если я ничего не напутал в расчетах

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

Н
На С++ в такое время ночи программу, точно не напишу . А завтра, если появиться время постараюсь. А может вместо с++ есть альтернативы? (Ну например Delphi)

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

Willow писал(а):

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

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

Программа на Python, реализующая нерекурсивный алгоритм:

def factorial(n):
  nf = 1
  for ix in range(n): nf = nf*(ix+1)
  return nf

def permutaions(l):
  p = list(l)
  yield tuple(p)

  for index in xrange(1, factorial(len(l))):
    div = 1
    for ix in range(1, len(p)):
      p[0:ix], p[ix] = p[1:ix+1], p[0]
      div = div*(ix+1)
      if index % div != 0:
        yield tuple(p)
        break

Использование:

## Ирония судьбы
for x in permutations(["надо","пить","меньше"]):  
  print " ".join(x)

[Drag]

Н писал(а):

не могу написать программу в С++, формулирующую все предложения, которые можно составить из словосочетаний "ваши прекрасные глаза ", "сулят"," мне", " сметрть", "прекрасная маркиза", "от любви". Все возможные перестановки.

Я б создал систему исчесления.
Количество вариантов N в степени N. В данном влучае 6 в степени 6 (46656 Вариантов) минус совпадения.
Каждой цитате по номеру.
Создать массив с количеством элементов равным количеству вариантов.
И произвести счет с отбрасыванием совподающих вариантов.
Например с 3-мя вариантами троичная система исчесления (27 вариантов).
111,112,113,121,122,123,131,132,133,211....
Если попадаются совпадения, Пример 122 или 131,Сочетание цитит пропускается.
Место в памяти понадобится если нужно сохронять все варианы комбиначий.
Подставить переменные для системы исчесления не так уж сложно.

[Werwolf]

2Drag
H просила перестановки, поэтому количество вариантов не 6 в степени 6, а 6!

[Drag]

Werwolf писал(а):

2Drag
H просила перестановки, поэтому количество вариантов не 6 в степени 6, а 6!

1: 123456
2: 123465
3: 123546
4: 123564
5: 123645
6: 123654
7: 124356
Уже 7 написал.

[DMVN]

Drag писал(а):

Werwolf писал(а):

2Drag
H просила перестановки, поэтому количество вариантов не 6 в степени 6, а 6!

Уже 7 написал.

Конечно, потому что имеется в виду 6!, то есть 6-факториал, а это, извините, 120.

[Drag]

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TForm1 = class(TForm)
Button1: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var a:array [1..6] of byte;
b:integer;
c:integer;
s1,s2,r:byte;
begin
a[1]:=1;
a[2]:=1;
a[3]:=1;
a[4]:=1;
a[5]:=1;
a[6]:=1;
c:=1;
b:=0;
while c<>0 do
begin
r:=1;
for s1:= 1 to 6 do
begin
for s2:= 1 to 6 do
begin
if s1<>s2 then
if a[s1]=a[s2] then r:=0;
end;
end;
b:=b+r;
a[6]:=a[6]+1;
if a[6]=7 then
begin
a[6]:=1;
a[5]:=a[5]+1;
if a[5]=7 then
begin
a[5]:=1;
a[4]:=a[4]+1;
if a[4]=7 then
begin
a[4]:=1;
a[3]:=a[3]+1;
if a[3]=7 then
begin
a[3]:=1;
a[2]:=a[2]+1;
if a[2]=7 then
begin
a[2]:=1;
a[1]:=a[1]+1;
if a[1]=7 then c:=0;
end;
end;
end;
end;
end;
end;
Label1.Caption:=inttostr(b);
end;

end.

На быструю руку если не допустил ошибки 720 вариантов.
Расчитывает на глаз за 0.3 сек.

[bugmaker]

Вообще, перестановку следует понимать так: для каждого элемента набора 1) убираем этот элемент из набора 2) осуществляем перестановку оставшихся, причём получаем соответствующее количество наборов 3) к каждому из полученных наборов добавляем убраный в п1 элемент. Всё прочее, как например вариант с системой исчисления по основанию ..., хоть и имеет место, но на деле только зря запутывает. В терминах списков это выражается довольно легко конечно:

(defparameter seq '("ваши прекрасные глаза" "сулят" "мне" "сметрть" "прекрасная маркиза" "от любви"))

(defun permutations (x)
    (if (null x)
        '(nil)
        (mapcan (lambda (e) (mapcar (lambda (p) (cons e p)) (permutations (remove e x :count 1 :test 'eq)))) x)))

(dolist (x (permutations seq)) (format t "~S~%" x))

На с++ конечно придётся помучить клавиатуру намного дольше. Вот прямая компиляция этой методики в с++:

#include <list>
#include <string>
#include <iostream> 
    
using namespace std;
        
typedef list<string> str_list;
typedef list<string>::iterator str_list_i;
typedef list<str_list> list_str_list;
typedef list<str_list>::iterator list_str_list_i;

list_str_list * get_all_perms (str_list &src) {
    list_str_list * l = new list_str_list;

    if (src.size ()) {
        for (str_list_i i = src.begin (); i != src.end (); i++) {
            str_list src1 = src;

            src1.erase (find (src1.begin (), src1.end (), (* i)));
            list_str_list * r = get_all_perms (src1);

            for (list_str_list_i j = r->begin (); j != r->end (); j++) {
                (*j).push_front (*i);
                l->push_back (*j);
            }
            delete r;
        }

    } else {
        l->push_back (* new str_list);
    }
    return l;
}

int main (int argc, char * argv) {
    str_list src;

    src.push_front ("ваши прекрасные глаза");
    src.push_front ("сулят");
    src.push_front ("мне");
    src.push_front ("сметрть");
    src.push_front ("прекрасная маркиза");
    src.push_front ("от любви");
    list_str_list &perms = * get_all_perms (src);
    for (list_str_list_i i = perms.begin (); i != perms.end (); i++) {
        for (str_list_i j = (*i).begin (); j != (*i).end (); j++) {
            cout << (*j) << " ";
        }
        cout << endl;
    }
}

ЗЫ прога заведомо не претендует на эффективность, т.к. я стремился главным образом к простоте и понятности примера.

ЗЗЫ На преподавателей, терзающих невинных дитёв таким уродством как с++, нужно жаловаться. В общество защиты жывотных.

ЗЗЗЫ Н, фотку в студию плз!