задача: Создайте все анаграммы из слова food — то есть все четырехбуквенные комбинации бинации f, о, о, d. Обобщите эту программу так, чтобы она получала на выходе строку а на выходе выдавала анаграммы. (Страуструп глава 18, задача 14)
От себя уточню задачу, выходом считаем вывод на экран, входом — входные параметры функций
Повестка обсуждения:
1) предлагаю реализовать на С++. Лично для себя уяснил, что по настоящему рекурсией ДААААВНО не пользовался.
2) Предлагаю покритиковать мою реализацию. У меня в голове вертится, что можно меньше памяти выделять, но что-то решение не родится. Вот проект: http://rsdn.ru/File/10424/dead_ostrich_18_14.rar В форум код не выкладываю, дабы те кто будут заниматься пунктом 1 случайно не подсмотрели.
3) И самое главное. Задача дана в главе "Алгоритмы и обьекты функции (STL)", так вот, не понятно на использование каких алгоритмов была дана задача??? В принципе я мог и без ротейт обойтись...
Здравствуйте, APTEC, Вы писали:
APT>задача: Создайте все анаграммы из слова food — то есть все четырехбуквенные комбинации бинации f, о, о, d. Обобщите эту программу так, чтобы она получала на выходе строку а на выходе выдавала анаграммы. (Страуструп глава 18, задача 14) APT>От себя уточню задачу, выходом считаем вывод на экран, входом — входные параметры функций
APT>Повестка обсуждения:
APT>1) предлагаю реализовать на С++. Лично для себя уяснил, что по настоящему рекурсией ДААААВНО не пользовался.
APT>2) Предлагаю покритиковать мою реализацию. У меня в голове вертится, что можно меньше памяти выделять, но что-то решение не родится. Вот проект: http://rsdn.ru/File/10424/dead_ostrich_18_14.rar В форум код не выкладываю, дабы те кто будут заниматься пунктом 1 случайно не подсмотрели.
APT>3) И самое главное. Задача дана в главе "Алгоритмы и обьекты функции (STL)", так вот, не понятно на использование каких алгоритмов была дана задача??? В принципе я мог и без ротейт обойтись...
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "food";
sort(s.begin(), s.end());
do {
cout << s << endl;
} while (next_permutation(s.begin(), s.end()));
return 0;
}
Здравствуйте, APTEC, Вы писали:
APT>задача: Создайте все анаграммы из слова food — то есть все четырехбуквенные комбинации бинации f, о, о, d. Обобщите эту программу так, чтобы она получала на выходе строку а на выходе выдавала анаграммы. (Страуструп глава 18, задача 14) APT>От себя уточню задачу, выходом считаем вывод на экран, входом — входные параметры функций
APT>Повестка обсуждения:
APT>1) предлагаю реализовать на С++. Лично для себя уяснил, что по настоящему рекурсией ДААААВНО не пользовался.
APT>2) Предлагаю покритиковать мою реализацию. У меня в голове вертится, что можно меньше памяти выделять, но что-то решение не родится. Вот проект: http://rsdn.ru/File/10424/dead_ostrich_18_14.rar В форум код не выкладываю, дабы те кто будут заниматься пунктом 1 случайно не подсмотрели.
Ты её тестировал?
Она выполняет все возможные перестановки массива, без оглядки на его содержимое. То есть N! перестановок.
А в слове food, например, две буквы o повторяются. Переставь их местами, что получишь? Вот.
Кстати говоря, у тебя глубина рекурсии равна длине массива . Для коротких массивов сойдёт...
APT>3) И самое главное. Задача дана в главе "Алгоритмы и обьекты функции (STL)", так вот, не понятно на использование каких алгоритмов была дана задача??? В принципе я мог и без ротейт обойтись...
Потому что алгоритм next_permutation — следующая (в лексикографическом порядке) перестановка — делает именно то, что требуется.
Ну а начинать нужно с самой "маленькой" (лексикографически), которую мы получаем с помощью сортировки по возрастанию — алгоритма sort.
Причём для массива уникальных элементов будет, как и ожидалось, N! перестановок, а для массива из X и Y одинаковых элементов ("fffoooo", X=3,Y=4) получим C((X+Y),X).
@echo off
if {%delayed_env%}=={} goto set_delayed_env
set str=food
call :sort %str%
goto :eof
:sort
set string=%1
set /a pos=0
:loop_len
set onechar=%%string:~%pos%,1%%
for /f "tokens=1,2 delims==" %%a in ('set onechar') do for /f %%c in ('echo %%b') do call :fill_array %%c array
if defined bAdded goto loop_len
set /a iCurrPos=1
set /a strlen=%pos%
:loop_sort
call :findmin %iCurrPos% %strlen%
call :swap %iCurrPos% %minidx%
set /a iCurrPos+=1
if %iCurrPos% lss %strlen% goto loop_sort
:main_loop
call :cat_chars %strlen%
echo %out_string%
call :perm %strlen%
if defined bWasPerm goto main_loop
goto :eof
:fill_array
set bAdded=
if /i {%1}=={echo} goto :eof
set bAdded=true
set /a pos+=1
set %2%pos%=%1
goto :eof
:findmin
set minelementTag=array%1
for /f "tokens=1,2 delims==" %%a in ('set %minelementTag%') do set minelement=%%b
set minidx=%1
for /l %%a in (%1,1,%2) do (
for /f "tokens=1,2 delims==" %%b in ('set array%%a') do (
call :comparelss %%c !minelement!
if defined bLess (
set minelement=%%c
set minidx=%%a
)
)
)
goto :eof
:comparelss
set bLess=
if /i [%1]==[echo] goto :eof
if %1 lss %2 set bLess=true
goto :eof
:swap
set /a iFirst=%1
set /a iSecond=%2
set chrFirst=array%iFirst%
set chrSecond=array%iSecond%
for /f "tokens=1,2 delims==" %%a in ('set %chrFirst%') do set chrTempFirst=%%b
for /f "tokens=1,2 delims==" %%a in ('set %chrSecond%') do set chrTempSecond=%%b
set %chrFirst%=%chrTempSecond%
set %chrSecond%=%chrTempFirst%
goto :eof
:extract_element
set /a iPos=%1
set iPosTag=%3%iPos%
for /f "tokens=1,2 delims==" %%a in ('set %iPosTag%') do set %2=%%b
goto :eof
:cat_chars
set /a curr_pos=1
set out_string=
:loop_cat
call :extract_element %curr_pos% chrTemp array
set out_string=%out_string%%chrTemp%
set /a curr_pos+=1
if %curr_pos% gtr %1 goto loop_cat_out
goto loop_cat
:loop_cat_out
goto :eof
:perm
set /a iIndex=%1 - 2
:perm_loop1
if %iIndex% geq 0 goto perm01
goto perm_loop1_out
:perm01
set /a iIndex1=%iIndex% + 1
set /a iIndex2=%iIndex% + 2
call :extract_element %iIndex1% iElem1 array
call :extract_element %iIndex2% iElem2 array
if %iElem1% geq %iElem2% goto perm02
goto perm_loop1_out
:perm02
set /a iIndex-=1
goto perm_loop1
:perm_loop1_out
if %iIndex% lss 0 goto perm_no_more
set /a iIndex=%1 - 1
:perm_loop2
set /a iIndex1=%iIndex% + 1
call :extract_element %iIndex1% iElem1 array
call :extract_element %iIndex% iElem array
if %iElem1% leq %iElem% goto perm_skip1
set /a jIndex=%1 - 1
:perm_loop3
set /a jIndex1=%jIndex% + 1
call :extract_element %jIndex1% jElem1 array
call :extract_element %iIndex% iElem array
if %jElem1% gtr %iElem% goto perm_loop3_out
set /a jIndex-=1
if %jIndex% leq %iIndex% goto perm_loop3_out
goto perm_loop3
:perm_loop3_out
set /a jIndex1=%jIndex% + 1
call :swap %iIndex% %jIndex1%
goto perm_loop2_out
:perm_skip1
set /a iIndex-=1
if %iIndex% leq 0 goto perm_loop2_out
goto perm_loop2
:perm_loop2_out
set /a jIndex=%1 - 1
:perm_loop4
set /a iIndex1=%iIndex% + 1
set /a jIndex1=%jIndex% + 1
call :swap %iIndex1% %jIndex1%
set /a jIndex-=1
set /a iIndex+=1
if %jIndex% leq %iIndex% goto perm_loop4_out
goto perm_loop4
:perm_loop4_out
set bWasPerm=true
goto :eof
:perm_no_more
set bWasPerm=
goto :eof
:set_delayed_env
set delayed_env=true
cmd.exe /v:on /c %0
goto :eof
Да в этой задаче можно было и без delayed environment variable expansion обойтись, просто я сначала что-то написал так, а потом переделывать уже было лень — мозг отказывался думать.
Здравствуйте, Кодт, Вы писали:
К>Это был J или K ?
Это K.
К>Кстати, а прокомментировать можно, ибо уж больно красиво... но загадочно.
На самом деле, не так уж красиво — я на поезд торопился. Первая строчка — известный рекурсивный генератор перестановок чисел от 0 до x-1. Вторая применяет эти перестановки к строке и фильтрует дубли.
. Для коротких массивов сойдёт...
Перекуём баги на фичи!
кортокий ито сколько? Вернее, начиная с какого размера "будет плохо"?
