| Вопрос: Перестановка значений массива | Добавлено: 06.02.07 12:36 |
Автор вопроса:  Ejara | ICQ: 151006307 |
|
Здравствуйте!
Задача такая: имеется одномерный динамический массив. Необходимо получить все возможные перестановки элементов массива без повторений. Получал много ответов типа "Да это фигня! Все делается рекурсивно!" и т.д. но тут барану ясно что рекурсивно, а КАК? Если можно хотел бы посмотреть на код. |
| Ответы | Всего ответов: 11 |
|
Номер ответа: 1 Автор ответа:  avdey ICQ: 219571279 Вопросов: 34 Ответов: 486 |
Профиль | | #1 | Добавлено: 06.02.07 13:13 |
|
Могу подсказать с количеством перестановок если все элементы разные
Msgbox (Ubound(Massiv) ^ Ubound(Massiv))
|
||
|
Номер ответа: 2 Автор ответа: ENIX ICQ: 238819245 Вопросов: 9 Ответов: 76 |
Профиль | | #2 | Добавлено: 06.02.07 13:51 |
| и -1 проде еще довабить надо...хотя хз) | ||
|
Номер ответа: 3 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #3 | Добавлено: 06.02.07 14:04 |
|
Тут возможно несколько случаев:
Если перестановки не обязательно должны быть расположены в лексикографическом порядке, то можно использовать рекурсивный метод, берется начальная перестановка: 1 2 3 4 5 И для нее перебираются все перестановки длины n-1 справа, т.е. до 1 5 4 3 2 Затем берется минимальный неиспользованный элемент и меняется местом с начальным 2 5 4 3 1 и операция повторяется. Если длина перестановки 1 или 2, то как осуществлять перебор всех перестановок очевидно. Если обязательна лексикографическая упорядоченность, то нужно использовать довольно хитрый алгоритм, реализацию которого можно найти, например, в STL: template<class _BidIt> inline
bool _Next_permutation(_BidIt _First, _BidIt _Last) { // permute and test for pure ascending, using operator< _DEBUG_RANGE(_First, _Last); _BidIt _Next = _Last; if (_First == _Last || _First == --_Next) return (false); for (; ; ) { // find rightmost element smaller than successor _BidIt _Next1 = _Next; if (_DEBUG_LT(*--_Next, *_Next1)) { // swap with rightmost element that's smaller, flip suffix _BidIt _Mid = _Last; for (; !_DEBUG_LT(*_Next, *--_Mid); ) ; std::iter_swap(_Next, _Mid); std::reverse(_Next1, _Last); return (true); } if (_Next == _First) { // pure descending, flip all std::reverse(_First, _Last); return (false); } } } Если нужно получать произвольную перестановку по ее номеру (их всего n!, а не n^n), то нужно использовать примерно такой алгоритм: #include <iostream>
using namespace std; int fact(int n){ int res = n ? n : 1; for(int i = 2; i < n; i++) res *= i; return res; } int main(){ int i, j, r; int n = 6, m; for(int cm = 0; cm < fact(n); cm++){ m = cm; int *a = new int [n]; // Использованные числа for(i = 0; i < n; i++) a[i] = 0; for(i = n; i > 0; i--){ int k = m / fact(i-1); for(j = 0, r = 0; j < n; j++){ if(!a[j]  r++;
if(r == k + 1) break; } a[j] = 1; cout << j + 1 << " "; m %= fact(i-1); } delete [] a; cout << endl; } return 0; } |
||
|
Номер ответа: 4 Автор ответа: ENIXICQ: 238819245 Вопросов: 9 Ответов: 76 |
Профиль | | #4 | Добавлено: 06.02.07 14:10 |
|
Можно попробывать без рекурсии, думаю сработает
Dim i&,j&, Fill$() For i = 0 To Ubound(Masiv) For j=i To Ubound(Masiv)-1 Fill = Masiv(i) & Masiv(j) Next Next Это пузырьком без рекурсии, может прокатит...А без повторения чтобы тут надо мозговать) Есть простое решении в теле подФора сделать еще один и сравнивать, но это может хорошо погрузить систему, т.е. зависит от размера первоначального масива. |
||
|
Номер ответа: 5 Автор ответа: ENIXICQ: 238819245 Вопросов: 9 Ответов: 76 |
Профиль | | #5 | Добавлено: 06.02.07 14:26 |
|
а не то, это сочетание с ошибками в коде)...
|
||
|
Номер ответа: 6 Автор ответа: avdeyICQ: 219571279 Вопросов: 34 Ответов: 486 |
Профиль | | #6 | Добавлено: 06.02.07 16:26 |
| Мда... че-то я переборщил... | ||
|
Номер ответа: 7 Автор ответа: FeverВопросов: 60 Ответов: 808 |
Профиль | | #7 | Добавлено: 06.02.07 19:25 |
2Sharp Ворвался  Мало того что C, так ишчо и кусок STL.
_DEBUG_RANGE
_DEBUG_LT
*_Next, *--_Mid
std::iter_swap(_Next, _Mid)
std::reverse(_Next1, _Last);
Там же функции, как все от мелкомягких, тесно интегрированы |
||
|
Номер ответа: 8 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #8 | Добавлено: 06.02.07 22:53 |
| Их смысл интуитивно понятен, весь алгоритм тут есть, а ENIX и avdey вообще не поняли задачи, как мне кажется. | ||
|
Номер ответа: 9 Автор ответа: Ejara ICQ: 151006307 Вопросов: 2 Ответов: 1 |
Профиль | | #9 | Добавлено: 07.02.07 09:30 |
|
Всем огромное спасибо за участие. все получилось, но проблемка в следующем: если в массиве более 7 элементов , то программа выполняется несколько часов....
так что косяк, рекурсия не подходит... |
||
|
Номер ответа: 10 Автор ответа: ViperICQ: 249094859 Вопросов: 0 Ответов: 310 |
Профиль | | #10 | Добавлено: 07.02.07 10:27 |
|
Всем огромное спасибо за участие. все получилось, но проблемка в следующем: если в массиве более 7 элементов , то программа выполняется несколько часов....
так что косяк, рекурсия не подходит... не верю! Показывай прогу! |
||
|
Номер ответа: 11 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #11 | Добавлено: 07.02.07 14:54 |
|
Ну смотря насколько больше 7 элементов Если раза в 2, то вполне может быть
|
||
Страница: 1 |