#include <algorithm>
#include <vector>
#include <conio.h>
using namespace std;
int main()
{
const int SIZE = 6; // Число элементов перестановки
const int nInv = 2; // Число инверсий
int perm[SIZE]; // Исходная перестановка
for(int i=0;i<SIZE;i++)
{
perm=i+1;
}
vector<int> array(perm, perm+SIZE);
bool bExist = true;
int cntPerm = 0;
while(bExist)
{
// Подсчет числа инверсий
int iCnt=0;
for(i=0;i<SIZE-1;i++)
{
if(array>array[i+1])iCnt++;
}
if(iCnt==nInv)
{
cntPerm++;
for(i=0;i<SIZE;i++)
{
printf("%3d ", array);
}
printf("\n");
}
bExist = next_permutation(array.begin(),array.end());
}
printf("Имеется %d перестановок с %d инверсиями\n\n", cntPerm, nInv);
printf("Нажмите любую клавишу...");
getch();
return 0;
}
Инверсии в перестановках
В общем, решаю я задачу:
Задана последовательность чисел от 1 до n.
Также задано число k, которое отображает некоторое число инверсий.
Надо найти количество всех перестановок из n элементов, которые содержат данное количество инверсий k.
P.S. Читала Кнута. Там задача поставлена и даже решена, но ничего не понятно. Какие-то мысли до меня доходя, но что бы их связать и получить программу....вряд ли.
Очень прошу помочь. Хотя бы намекните, за что зацепиться... (Кнут уверяет, что задача имеет очень важное практическое значение).
Задана последовательность чисел от 1 до n.
Также задано число k, которое отображает некоторое число инверсий.
Надо найти количество всех перестановок из n элементов, которые содержат данное количество инверсий k.
P.S. Читала Кнута. Там задача поставлена и даже решена, но ничего не понятно. Какие-то мысли до меня доходя, но что бы их связать и получить программу....вряд ли.
Очень прошу помочь. Хотя бы намекните, за что зацепиться... (Кнут уверяет, что задача имеет очень важное практическое значение).
Цитата:
Originally posted by SunLine
В общем, решаю я задачу:
...
...
Какие-то мысли до меня доходя, но что бы их связать и получить программу....вряд ли.
В общем, решаю я задачу:
...
...
Какие-то мысли до меня доходя, но что бы их связать и получить программу....вряд ли.
Обычно люди не лукавлят. типа "В общем, решаю я задачу", а пишут как есть: "Дали задачу, но я даже не знаю с какой стороны подойти.........HEEEEEEEELP!!!" :)
Проще всего это решить с использованием STL.
Код:
1. Надеюсь ты пишешь на C.
2. Не знаю правильно ли подсчитываю число инверсий: если элемент i больше за элемента i+1, тогда это одна инверсия.
Цитата:
Обычно люди не лукавлят. типа "В общем, решаю я задачу", а пишут как есть: "Дали задачу, но я даже не знаю с какой стороны подойти.........HEEEEEEEELP!!!" :)
Нет, именно РЕШАЮ Я ЗАДАЧУ. Не задали, не требуют, и сроки не поджимают...
Маленькое лирическое отступление:
Надеюсь, Вам знакомо такое чувство, когда не хочется бросать начатое дело. Обольстившись несложным на первый взгляд условием, но потом натолкнувшись на трудности, просто взять и откинуть задачу, подписавшись этим в собственной слабости...
Понимаю, Вам иогло показаться, что я просто перекладываю свои проблемы на чужие плечи. Но это не так! Мне действительно важно ПОНЯТЬ. Я не прошу РЕШИТЬ за меня, я прошу НАМЕКНУТЬ с тем, чтобы потом самой дойти до решения...
1. Надеюсь ты пишешь на C.
Надеюсь, Вы не думаете, что я знаю только азы ПРОЛОГа?
В любом случае, спасибо Вам за код.
К сожалению, моих знаний не хватает, чтобы вот так с ходу, бегло его просмотрев, сразу же убедиться в его истинности. Поэтому комментарии пока опускаю.
Хорошо. Тогда намек. Алгоритм генерации всех перестановок c минимальным числом транспозиций, на псевдокоде.
Это из книги Липский: Комбинаторика для программистов. У меня есть и Кнут. Не сказал бы, что архи хорошая книга.
Ну как на счет мыслей? Они уже доходят связанные? Или все еще нет? :)
Код:
begin
for i:=1 to n do begin
P:=i; C:=1; PR:=истина;
end;
C[n]:=0;
write(P[1],...,P[n]);
i:=1;
while i<n do begin
i:=1; x:=0;
while C=n-i+1 do begin
PR:=not PR; C:=1;
if PR then x:=x+1;
i:=i+1;
end;
if i<n then begin
if PR then k:=C+x
else k:=n-i+1-C+x;
P[k]:=P[k+1];
write(P[1],...,P[n]);
C:=C+1;
end;
end;
end;
for i:=1 to n do begin
P:=i; C:=1; PR:=истина;
end;
C[n]:=0;
write(P[1],...,P[n]);
i:=1;
while i<n do begin
i:=1; x:=0;
while C=n-i+1 do begin
PR:=not PR; C:=1;
if PR then x:=x+1;
i:=i+1;
end;
if i<n then begin
if PR then k:=C+x
else k:=n-i+1-C+x;
P[k]:=P[k+1];
write(P[1],...,P[n]);
C:=C+1;
end;
end;
end;
Ну как на счет мыслей? Они уже доходят связанные? Или все еще нет? :)
Премного благодарна....
Рассмотрела код С.
Сразу же оговорка: инверсия - это такое расположение элементов в перестановке, когда больший по значению элемент располагается левее меньшего. И одним циклом число инверсий вы никак не подсчитаете. Поэтому строки кода
for(i=0;i<SIZE-1;i++)
if(array>array[i+1])iCnt++;
заменяю следующими:
for(int i=1;i<SIZE;i++)
for(int j=0;j<i;j++)
if(array<array[j])iCnt++;
Далее, получаем простой, тупой перебор всех возможных перестановок из данного числа элементов, которое равно n!
Конечно, когда n невелико, программа работает исправно и выдает правильный результат. Но при увеличении n наблюдается "комбинаторный взрыв", когда значение n! стремительно возрастает.
Наверное, мне следовало упомянуть, что условие задачи предполагает, что 1<=n<=20
И в разумное время программа не уложиться, перебираю, скажем, 14! различных перестановок...
Чем меня заинтересовал Кнут - так это его стремлением к оптимизации алгоритмов. В его книге я не встретила предложения тупо пересчитать все перестановки на предмет наличия в них заданого числа инверсий...
К сожалению, то, что он предлагает, мне не понятно настолько, я повторюсь, чтобы написать программу.
И я бы была признательна, если бы мне немного разъяснили его алгоритм.
Рассмотрела код С.
Сразу же оговорка: инверсия - это такое расположение элементов в перестановке, когда больший по значению элемент располагается левее меньшего. И одним циклом число инверсий вы никак не подсчитаете. Поэтому строки кода
for(i=0;i<SIZE-1;i++)
if(array>array[i+1])iCnt++;
заменяю следующими:
for(int i=1;i<SIZE;i++)
for(int j=0;j<i;j++)
if(array<array[j])iCnt++;
Далее, получаем простой, тупой перебор всех возможных перестановок из данного числа элементов, которое равно n!
Конечно, когда n невелико, программа работает исправно и выдает правильный результат. Но при увеличении n наблюдается "комбинаторный взрыв", когда значение n! стремительно возрастает.
Наверное, мне следовало упомянуть, что условие задачи предполагает, что 1<=n<=20
И в разумное время программа не уложиться, перебираю, скажем, 14! различных перестановок...
Чем меня заинтересовал Кнут - так это его стремлением к оптимизации алгоритмов. В его книге я не встретила предложения тупо пересчитать все перестановки на предмет наличия в них заданого числа инверсий...
К сожалению, то, что он предлагает, мне не понятно настолько, я повторюсь, чтобы написать программу.
И я бы была признательна, если бы мне немного разъяснили его алгоритм.
Цитата:
Originally posted by SunLine
И я бы была признательна, если бы мне немного разъяснили его алгоритм.
И я бы была признательна, если бы мне немного разъяснили его алгоритм.
По всей вероятности это в третьем томе. Но какой алгоритм? Хотя бы номер страницы.
Цитата:
Originally posted by Mоngооsе
По всей вероятности это в третьем томе. Но какой алгоритм? Хотя бы номер страницы.
По всей вероятности это в третьем томе. Но какой алгоритм? Хотя бы номер страницы.
В самом начале третьего тома, буквально 20-тые страницы (Кнут в электронном варианте, оригинальные номера страничек не указаны...)
Цитата:
Originally posted by SunLine
В самом начале третьего тома, буквально 20-тые страницы (Кнут в электронном варианте, оригинальные номера страничек не указаны...)
В самом начале третьего тома, буквально 20-тые страницы (Кнут в электронном варианте, оригинальные номера страничек не указаны...)
Комбинаторные свойства перестановок (глава 5.1) начинается с 25й страницы. Но здесь я не вижу такого алгоритма, которая генерирует только перестановки с k инверсиями. Пишется только о какой то таблице инверсий. Хотя бы первое предложение абзаца :)
Это нужно закодировать ф-ю In(k)? Таблица 1?
10я формула?
10я формула?
Цитата:
Originally posted by Mоngооsе
Это нужно закодировать ф-ю In(k)? Таблица 1?
10я формула?
Это нужно закодировать ф-ю In(k)? Таблица 1?
10я формула?
Меня смущает условие после этой формулы: n>=k
Что делать, когда k>n?
Цитата:
Originally posted by SunLine
Меня смущает условие после этой формулы: n>=k
Что делать, когда k>n?
Меня смущает условие после этой формулы: n>=k
Что делать, когда k>n?
Эта формула для случая k>=n. Для k<n используется 9я формула.
В 10й ф-ле условием остановки может быть
(3*j**2-j)/2 >= k
Можно определить максимальное число инверсий для перестановки заданой длины, это
max_in=n*(n-1)/2
Это может пригодиться для проверки - вдруг перестановок с числом инверсий k вообще не сущесвует?
С симметрией тоже ясно:
if(k>(max_in-k))k=max_in-k;
...
max_in=n*(n-1)/2
Это может пригодиться для проверки - вдруг перестановок с числом инверсий k вообще не сущесвует?
С симметрией тоже ясно:
if(k>(max_in-k))k=max_in-k;
...
Цитата:
Originally posted by SunLine
Можно определить максимальное число инверсий для перестановки заданой длины, это
max_in=n*(n-1)/2
Это может пригодиться для проверки - вдруг перестановок с числом инверсий k вообще не сущесвует?
С симметрией тоже ясно:
if(k>(max_in-k))k=max_in-k;
...
Можно определить максимальное число инверсий для перестановки заданой длины, это
max_in=n*(n-1)/2
Это может пригодиться для проверки - вдруг перестановок с числом инверсий k вообще не сущесвует?
С симметрией тоже ясно:
if(k>(max_in-k))k=max_in-k;
...
??? нужно закодировать 9ю и 10ю формулу. Работа макс. на час. :)
Цитата:
Originally posted by Mоngооsе
Эта формула для случая k>=n. Для k<n используется 9я формула.
В 10й ф-ле условием остановки может быть
(3*j**2-j)/2 >= k
Эта формула для случая k>=n. Для k<n используется 9я формула.
В 10й ф-ле условием остановки может быть
(3*j**2-j)/2 >= k
формула (10) при условии n>=k
формула (9) при условии n>k
Так написано...
Цитата:
Originally posted by SunLine
формула (10) при условии n>=k
формула (9) при условии n>k
Так написано...
формула (10) при условии n>=k
формула (9) при условии n>k
Так написано...
Опечатка. 10 для k>=n.
Это видно из табл.1.
Цитата:
Originally posted by Mоngооsе
Опечатка. 10 для k>=n.
Это видно из табл.1.
Опечатка. 10 для k>=n.
Это видно из табл.1.
Благодорю. Завтра попробую написать код. Если возникнут сложности, смогу ли я обратиться к вам за помощью?
Цитата:
Originally posted by SunLine
Благодорю. Завтра попробую написать код. Если возникнут сложности, смогу ли я обратиться к вам за помощью?
Благодорю. Завтра попробую написать код. Если возникнут сложности, смогу ли я обратиться к вам за помощью?
Конечно, буду рад помочь :)
SunLine - мое вам почтение как девушке программисту. К сожалению по теме помочь ни чем не могу. Я тут прочитал, что Кнут в электронном виде, можно узнать - откуда, т.е. где можно скачать?
Буду очень благодарен, если подскажете.
Буду очень благодарен, если подскажете.
Цитата:
Originally posted by pacific_7
SunLine - мое вам почтение как девушке программисту.
SunLine - мое вам почтение как девушке программисту.
Спасибо...
Цитата:
Originally posted by pacific_7
Я тут прочитал, что Кнут в электронном виде, можно узнать - откуда, т.е. где можно скачать?
Буду очень благодарен, если подскажете.
Я тут прочитал, что Кнут в электронном виде, можно узнать - откуда, т.е. где можно скачать?
Буду очень благодарен, если подскажете.
К сожалению, я не в курсе, где можно скачать "Исскуство программирования". Мне трехтомник достался на диске в формате djvu (дежавю). Весит 18 Мб. Но я абсолютно не против выслать его вам на e-mail, если вы его оставите.
Не знаю, насколько правомерно с моей стороны распростронять такие вещи, но может возможно вывесить книгу на каком-нибудь сайте - я думаю, она понадобиться не только вам...
Цитата:
Originally posted by SunLine
Не знаю, насколько правомерно с моей стороны распростронять такие вещи, но может возможно вывесить книгу на каком-нибудь сайте - я думаю, она понадобиться не только вам...
Не знаю, насколько правомерно с моей стороны распростронять такие вещи, но может возможно вывесить книгу на каком-нибудь сайте - я думаю, она понадобиться не только вам...
Да, мне тоже для коллекции электронного Кнута очень не хватает.
Однако, SunLine, перед тем как выставлять её куда-нибудь, посмотрите внимательно, нет ли там фразы "Права защищены, и мы будем преследовать SunLine и всё её потомство до десятого колена по всей строгости закона"?
Цитата:
Originally posted by sq_deep
Однако, SunLine, перед тем как выставлять её куда-нибудь, посмотрите внимательно, нет ли там фразы "Права защищены, и мы будем преследовать SunLine и всё её потомство до десятого колена по всей строгости закона"?
Однако, SunLine, перед тем как выставлять её куда-нибудь, посмотрите внимательно, нет ли там фразы "Права защищены, и мы будем преследовать SunLine и всё её потомство до десятого колена по всей строгости закона"?
Посмотрела. Все книги начинаются с предисловия к русскому изданию. Про права ничего не сказано. Может, страничка с этими словами не была отсканирована?
Уважаемые программисты, имеющие на руках Кнута в бумажном варианте, убедительная просьба: внимательно изучите первые странички книги, ну там где всякие выходные данные идут. Там что-то сказано про защищенные права?
Цитата:
Originally posted by SunLine
Посмотрела. Все книги начинаются с предисловия к русскому изданию. Про права ничего не сказано. Может, страничка с этими словами не была отсканирована?
Уважаемые программисты, имеющие на руках Кнута в бумажном варианте, убедительная просьба: внимательно изучите первые странички книги, ну там где всякие выходные данные идут. Там что-то сказано про защищенные права?
Посмотрела. Все книги начинаются с предисловия к русскому изданию. Про права ничего не сказано. Может, страничка с этими словами не была отсканирована?
Уважаемые программисты, имеющие на руках Кнута в бумажном варианте, убедительная просьба: внимательно изучите первые странички книги, ну там где всякие выходные данные идут. Там что-то сказано про защищенные права?
Мой бумажный вариант 197х года издания. Даже и смотреть не буду. Там точно такого нет. А в тираже, который печатался года 3 назад — тут и к бабке не ходи — точно есть. Однако, относится ли это к электронной книге — это вопрос. Бог его знает. Обычно авторские права живут 20 лет, и этот срок уже прошёл, так что копирайты последнего издания могут относиться к переводу, если он сделан специально для этого издания, или к оформлению или к чему-нибудь в этом роде.
Могу предложить разместить книгу на народе.ру так чтобы невозможно было понять, кто это сделал. Но там сайт автоматически уничтожается, если на него долго (примерно год) никто не заходит. Хотите, положу?
Цитата:
Originally posted by sq_deep
Могу предложить разместить книгу на народе.ру так чтобы невозможно было понять, кто это сделал. Но там сайт автоматически уничтожается, если на него долго (примерно год) никто не заходит. Хотите, положу?
Могу предложить разместить книгу на народе.ру так чтобы невозможно было понять, кто это сделал. Но там сайт автоматически уничтожается, если на него долго (примерно год) никто не заходит. Хотите, положу?
Да пожалуйста!
Стучите в Аську 259171618
там все обсудим
Цитата:
Originally posted by SunLine
Да пожалуйста!
Стучите в Аську 259171618
там все обсудим
Да пожалуйста!
Стучите в Аську 259171618
там все обсудим
ICQ я не пользуюсь. Сейчас уже должен уйти.
Завтра свяжусь с вами по почте и договоримся.
А на фига такому зверскому програмисту Кнут? Твоя единственная книга - МСДН, автор Блин Гей, тьху ты Билл Гейтс.
Цитата:
Originally posted by sq_deep
Могу предложить разместить книгу на народе.ру так чтобы невозможно было понять, кто это сделал. Но там сайт автоматически уничтожается, если на него долго (примерно год) никто не заходит. Хотите, положу?
Могу предложить разместить книгу на народе.ру так чтобы невозможно было понять, кто это сделал. Но там сайт автоматически уничтожается, если на него долго (примерно год) никто не заходит. Хотите, положу?
Я то же! В смысле хочу видеть Кнута на народе. Желательно как-нибудь по отдельности каждый том - за один раз мне столько выкачивать напряжно, но вообще - как у вас получится.
Заранее спасибо!
офтоп: sq_deep - почему аськой не пользуетесь? Это не порицание, просто мне интересно ваша точка зрения. К слову: я ICQ то же не пользуюсь.
Цитата:
Originally posted by Dart Bobr
А на фига такому зверскому програмисту Кнут? Твоя единственная книга - МСДН, автор Блин Гей, тьху ты Билл Гейтс.
А на фига такому зверскому програмисту Кнут? Твоя единственная книга - МСДН, автор Блин Гей, тьху ты Билл Гейтс.
Ты хоть знаешь, что такое MSDN? Кстати БГ думаю (практически уверен) ни малейшего отношешния не имеет к его созданию в качестве автора.
И вообще - иди контроллеры программируй.
Бобрик, не нарывайтесь. Я пока ещё не подключился к всеобщей травле вас...
Сначала всем:
Господа, не сочтите, пожалуйста, что я учу вас всех жить. Уверен, что вы умеете делать это не хуже меня.
Однако, перестаньте слишком агрессивно нападать на некоторых участников форума. Каждый имеет своё мнение и должен высказывать его, но только корректно. Французы, например, считают, что свбода человека заканчивается у кончика носа соседа. Да и в конце концов нет доблести в том, чтобы всем воевать с одним. Мы же с вами тут не на зоне, а в интеллектуальном обществе. «Ребята, давайте жить дружно».
А теперь персонально для pacific_7
Господа, не сочтите, пожалуйста, что я учу вас всех жить. Уверен, что вы умеете делать это не хуже меня.
Однако, перестаньте слишком агрессивно нападать на некоторых участников форума. Каждый имеет своё мнение и должен высказывать его, но только корректно. Французы, например, считают, что свбода человека заканчивается у кончика носа соседа. Да и в конце концов нет доблести в том, чтобы всем воевать с одним. Мы же с вами тут не на зоне, а в интеллектуальном обществе. «Ребята, давайте жить дружно».
А теперь персонально для pacific_7
Цитата:
Originally posted by pacific_7
sq_deep - почему аськой не пользуетесь?
sq_deep - почему аськой не пользуетесь?
Аська привносит нервозность в жизнь. Вот я сейчас пишу письмо, подбираю слова, стараюсь или наоборот расслабился, медитирую... И тут вдруг — бац! — откуда ни возьмись школьный приятель прорезался! Я не против одноклассников, но только тогда, когда я хочу, а не когда надо. А для срочных дел всегда есть телефон.
— Вот за это я и не люблю Асек...
— Ты их просто неправильно готовишь.
Цитата:
Originally posted by sq_deep
Бобрик, не нарывайтесь. Я пока ещё не подключился к всеобщей травле вас...
Бобрик, не нарывайтесь. Я пока ещё не подключился к всеобщей травле вас...
Я щас под стол залезу со страху. А кто это тут собственно травит кого? Дельфовщики распоясались?
Пойду ка я на свой любимый wasm.ru.
Кстати если Билл Гейтс не имеет ни малейшего отношения к МСДН, то кто-то здесь явно гонит(вроде не я), ибо ее можно скачать на сайте мелкомягкой фермы.
Вернемся к нашим баранкам...
Разбираю формулу (10) - Кнут, том 3.
Там сначала идут первые слагаемые, а потом обший случай, который зависит от j
Как я понимаю, начальное значение j=1 (а может быть и j=0), с условием остановки мы вроде тоже выяснили (выполнять пока U(j)<=k)
Но дальше, когда я исходя из общего случая начинаю просчитывать элементы суммы, то никак не выхожу на данную Кнутом последовательность.
Хотелось бы прояснить этот момент...
Разбираю формулу (10) - Кнут, том 3.
Там сначала идут первые слагаемые, а потом обший случай, который зависит от j
Как я понимаю, начальное значение j=1 (а может быть и j=0), с условием остановки мы вроде тоже выяснили (выполнять пока U(j)<=k)
Но дальше, когда я исходя из общего случая начинаю просчитывать элементы суммы, то никак не выхожу на данную Кнутом последовательность.
Хотелось бы прояснить этот момент...
Цитата:
Originally posted by SunLine
Вернемся к нашим баранкам...
Разбираю формулу (10) - Кнут, том 3.
Там сначала идут первые слагаемые, а потом обший случай, который зависит от j
Как я понимаю, начальное значение j=1 (а может быть и j=0), с условием остановки мы вроде тоже выяснили (выполнять пока U(j)<=k)
Но дальше, когда я исходя из общего случая начинаю просчитывать элементы суммы, то никак не выхожу на данную Кнутом последовательность.
Хотелось бы прояснить этот момент...
Вернемся к нашим баранкам...
Разбираю формулу (10) - Кнут, том 3.
Там сначала идут первые слагаемые, а потом обший случай, который зависит от j
Как я понимаю, начальное значение j=1 (а может быть и j=0), с условием остановки мы вроде тоже выяснили (выполнять пока U(j)<=k)
Но дальше, когда я исходя из общего случая начинаю просчитывать элементы суммы, то никак не выхожу на данную Кнутом последовательность.
Хотелось бы прояснить этот момент...
imho, снова опечатка.
Код:
((n + k - uj - 1) ...
(-1)**j (( )+ ...
(( k - uj [color=red]+ 1[/color] ) ...
(-1)**j (( )+ ...
(( k - uj [color=red]+ 1[/color] ) ...
(3*j**2-j)/2 и (3*j**2+j)/2
это будет
j = 1 1 2
j = 2 5 6
j = 3 11 12
и если k равно одному из этих чисел, к сумме добавить или отнять единицу в зависимости от соотв. j.
т.е. (-1)**j.