Перестановки и разработки алгоритм генерации комбинации
Я предполагаю записать алгоритм для распечатки всех возможных комбинаций заданных пар ‘<> ‘, Я пытался разработать алгоритм для решения этой проблемы, но я думаю, что это не правильно, потому что я понимаю, что эта проблема связана с перестановками [nPr] & допустим, для заданного ввода 5 он должен создать 120 комбинаций (5P5 = 120), но мой код генерирует только 81.
In my code have tried to generate all possible combinations by placing every element at every place one by one, but now I am little confused about how correct this approach is?
Дело в том, что, скорее всего, я не в состоянии понять реальную концепцию «создания подмножеств / комбинаций / перестановок» (хотя теоретически я знаю, что это такое и как их вычислять)
Я не ищу полный окончательный «код с ложкой», но что-то, что могло бы объяснить мне «что я должен делать», из которого я мог бы извлечь шаги, понять концепцию и разработать свою собственную.
If possible something extending or tweaking my current coding to achieve the right result would be easier for me to understand.
void permute()
{
string str=”<><><>”;
char buck=' ';
for(int a=0;a<str.length()-1;a++)
{
for(int b=0;b<str.length()-1;b++){
cout<<str<<endl;
buck=str[b];
str[b]=str[b+1];
str[b+1]=buck;
}
}
}
Я пытался понять, что я должен делать, но я все еще изо всех сил, любая помощь или руководство были бы действительно полезны.
Спасибо
From 'all combinations' i mean printing out all the possible ways given set of characters can be arranged, lets say for 2 pairs '<><>' it should be like: <><>,><<>,><<>,><><,<<>>,>><< ... ... ...
Решение
C ++ обеспечивает bool std::next_permutation(Iterator first, Iterator last) это изменяет содержание (first, last), чтобы быть следующей перестановкой в последовательности, возвращая истину, если есть больше перестановок, или ложь, если это последняя перестановка. Сначала необходимо отсортировать список (используя std::sort(Iterator first, Iterator last)), и отсортированный список формирует первую перестановку.
Вы можете взаимодействовать с этими алгоритмами, используя str.begin() а также str.end(),
НОТА: Поскольку ваш набор данных содержит повторяющиеся элементы, не все перестановки возможны (некоторые будут дубликатами других записей). То есть:
string : permutations
-------:-------------
abcd : 24
<><> : 6
abcdef : 720
<><><> : 20
Если вы действительно хотите все перестановки (включая дубликаты), вы можете иметь int indices = { 0, 1, 2, 3, 4, 5 }; массив, на котором вы запускаете перестановки и затем печатаете str[indices[0]] через str[indices[5]] для каждой перестановки.
Это может дать вам представление о вашем алгоритме и о том, что происходит не так. То есть, он может служить ссылкой для сравнения вашего алгоритма.
Другие решения
Согласно моему тесту у него есть 42 решения:
function placeBrackets(n)
{
var placeBracketsRecur = function(prefix, remainingOpen, remainingClosed)
{
if(remainingClosed == 0)
{
document.write(prefix + "<br/>");
return;
}
if(remainingOpen > 0)
{
placeBracketsRecur(prefix + "(", remainingOpen - 1, remainingClosed);
}
if(remainingOpen < remainingClosed)
{
placeBracketsRecur(prefix + ")", remainingOpen, remainingClosed - 1);
}
}
placeBracketsRecur("", n, n);
}
///выход
((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()
detector