Форум программистов, компьютерный форум CyberForum.ru

Все возможные перестановки элементов заданного массива - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 55, средняя оценка - 4.95
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
06.02.2013, 20:52     Все возможные перестановки элементов заданного массива #1
Помогите вывести на консоль все возможные перестановки элементов заданного массива
C++
1
void printPermutations (int items [ ], int itemsLength) { ... }
Пример (порядок вывода результатов может отличаться):
C++
1
2
3
4
5
6
7
8
int numbers[ ] = {1, 2, 3};
printPermutations (numbers , 3);
123
132
213
231
312
321
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Veselchak
1 / 1 / 0
Регистрация: 06.02.2013
Сообщений: 43
06.02.2013, 22:08     Все возможные перестановки элементов заданного массива #2
Все возможные перестановки элементов заданного массива, ето количество елементов поднесенное к факториалу.
Тоесть если масив состоит из 5 елементов, то нужен факториал 5. Формула: !5=1*2*3*4*5;
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
06.02.2013, 22:23     Все возможные перестановки элементов заданного массива #3
Цитата Сообщение от Veselchak Посмотреть сообщение
Все возможные перестановки элементов заданного массива, ето количество елементов поднесенное к факториалу.
Тоесть если масив состоит из 5 елементов, то нужен факториал 5. Формула: !5=1*2*3*4*5;
человек спросил не количество возможных перестановок, а сами перестановки...
по теме - если никто не опередит, сейчас набросаю код, как доделаю по работе один момент

Добавлено через 10 минут
прошу

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
 
using namespace std;
 
void printPermutations (int items [], int itemsLength)
{
    vector<int> v;
    for (int i=0; i!=itemsLength; ++i) v.push_back(items[i]); 
 
    while (next_permutation(v.begin(), v.end() ) ) 
    { 
        copy(v.begin(), v.end(), ostream_iterator<int>(cout, ""));
        cout << endl;
    }
}
 
 
int main() 
{ 
    
    const int sizeArray = 3;
    int Array [sizeArray] = {1,2,3};
    
    printPermutations(Array,sizeArray);
    
    return 0;
}
hokoko
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 13
06.02.2013, 22:33  [ТС]     Все возможные перестановки элементов заданного массива #4
Спасибо
Veselchak
1 / 1 / 0
Регистрация: 06.02.2013
Сообщений: 43
06.02.2013, 22:44     Все возможные перестановки элементов заданного массива #5
Виноват))
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.02.2013, 22:45     Все возможные перестановки элементов заданного массива #6
Цитата Сообщение от abit Посмотреть сообщение
next_permutation(
Что это за функция такая? Что это за язык? Здесь раздел С++!
Моё решение на С++:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
void solve(int items [], int size, int l=0){
    int i;
    if (l==size){
        for (i=0; i<size; i++)
          printf("%d ", items[i]);  
        putchar('\n');
    }
    else
        for (i=l; i<size; i++){
            if (l^i){
                 items[l]^= items[i];
                 items[i]^= items[l];
                 items[l]^= items[i];
                 solve(items, size, l+1);
                 items[l]^= items[i];
                 items[i]^= items[l];
                 items[l]^= items[i];
            }else
                solve(items, size, l+1);
        }
}
int main(int argc, char *argv[]){  
    int arr[]={1, 2, 3, 4};
    solve(arr, 4);
    return 0;
}
ИМХО лучше читаемо
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
06.02.2013, 22:54     Все возможные перестановки элементов заданного массива #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Что это за функция такая? Что это за язык? Здесь раздел С++!
значит, боюсь, вы не совсем знаете язык C++...

можете убедиться это работает - http://liveworkspace.org/code/375xm7$0

про функцию почитайте тут - http://cplusplus.com/reference/algor...xt_permutation

и прекратите изобретать велосипеды, всё уже давно придумано, учите С++, раз знаете, что находитесь в разделе С++
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
06.02.2013, 22:54     Все возможные перестановки элементов заданного массива #8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Что это за функция такая? Что это за язык? Здесь раздел С++!
Моё решение на С++:
Я вас огорчу но Вам в раздел : "Основы С"

Пример выше симпотишный и довольно изящный )
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
06.02.2013, 22:57     Все возможные перестановки элементов заданного массива #9
Тупой нерекурсивный вариант.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int main()
{
    const int n=4;
    int a[n];
    int i,j,k,i1,i2;
    int temp;
    for(i=0; i<n; i++) a[i]=i+1;
    for(;;) {
        for(i=0; i<n; i++) cout << a[i] << " ";
        cout << '\n';
        for(j=n-1; j>0; j--)
            if(a[j]>a[j-1]) break;
        if(j==0) return 0;
        j--;
        for(k=n-1; k>j; k--) {
            if(a[k]>a[j]) {
                temp=a[k];
                a[k]=a[j];
                a[j]=temp;
                break;
            }
        }
        for(i1=j+1,i2=n-1; i1<i2; i1++,i2--) {
            temp=a[i1];
            a[i1]=a[i2];
            a[i2]=temp;
        }
    }
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.02.2013, 23:14     Все возможные перестановки элементов заданного массива #10
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Я вас огорчу но Вам в раздел : "Основы С"
Мой ответ на С++. На Си бы не скомпилировалось. И я ничуть не огорчился бы, даже если это было так.

Цитата Сообщение от abit Посмотреть сообщение
значит, боюсь, вы не совсем знаете язык C++...
Это не значит, что совсем не знаю. Нет, этот пример с использованием <algorithm> ещё что... а вот некоторые вообще всякую экзотику вроде boost используют, словно эта библиотека часть C++!!!
abit
06.02.2013, 23:27
  #11

Не по теме:


Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Это не значит, что совсем не знаю. Нет, этот пример с использованием <algorithm> ещё что... а вот некоторые вообще всякую экзотику вроде boost используют, словно эта библиотека часть C++!!!
boost это конечно хорошо, но STL уже давно входит в С++...
я если Вас задел, извините...
дело обстояло так, что я совсем недавно стал учить С++, до этого был fasm, FPC и Haskell, точнее - даже месяца не прошло, как я купил свою первую книжку по С++ и знакомый программист мне посоветовал брать сразу STL и Qt... я залпом и стал читать книги Cкотта Мейерса (ибо очень интересно), поэтому в базовом языке C - я очень слаб (

Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
06.02.2013, 23:36     Все возможные перестановки элементов заданного массива #12
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
printf("%d ", items[i]); *
* * * * putchar('\n');
Старый сишный стиль вывода. Я не говорю +/- я говорю что это Си. Любую книгу можете открыть и увидите там это.

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
#include <stdio.h>
#include <cstdio> - вот хидер С++
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
int items []
Давайте в рекурсивной функции на стеке копии массивов создавать =)
coloc
погромист
 Аватар для coloc
409 / 245 / 15
Регистрация: 27.08.2012
Сообщений: 550
Завершенные тесты: 1
06.02.2013, 23:39     Все возможные перестановки элементов заданного массива #13
разработчики дума 3 вообще не юзали стл и шаблоны. Они ,,изобретали велосипеды,, для конкретных задач.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.02.2013, 23:49     Все возможные перестановки элементов заданного массива #14
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Давайте в рекурсивной функции на стеке копии массивов создавать =)
не надо тут про копию на стеке. всё по указателю передаётся. Не думаешь же ты, что в стек запихивается неизвестное количество элементов массива неизвестной величины.

Добавлено через 2 минуты
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Старый сишный стиль вывода. Я не говорю +/- я говорю что это Си. Любую книгу можете открыть и увидите там это.
В каком году его признали устаревшим, можно уточнить? Да и не забывай, что язык "Си" вообще, безотносительно ввода/вывода, сейчас повсюду используется и сдавать позиции не намерен.
abit
06.02.2013, 23:58
  #15

Не по теме:


Цитата Сообщение от coloc Посмотреть сообщение
разработчики дума 3 вообще не юзали стл и шаблоны. Они ,,изобретали велосипеды,, для конкретных задач.
не уловил связь с doom 3...
дай мне 10 нормальных программистов, 2-3 дизайнеров и 1 сценариста, 5-6 лет, и приличный бюджет, чтобы содержать эту команду, я тебе забацаю аналог дум-3 не то что без STL - а на ассемблере, но когда речь идёт о простых задачах, лучше пользоваться общепринятыми и проверенными инструментами, это быстрее, удобнее и проверенно... всё же вы не разработчик дум-3, чтобы плевать на стандарты

HighPredator
06.02.2013, 23:58
  #16
 Комментарий модератора 
Господа, от темы не отклоняйтесь.
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 00:46     Все возможные перестановки элементов заданного массива #17
Я думаю, что если задача учебная, то не стоит использовать уже изобретенный велосипед.
Цель задачи - научить изобретать, а обучение как раз и начинают с велосипедов.
Сколько разных задач проходит на тему сортировки, но никто ведь не предлагает решать их с использованием функции sort, которая уже написана и имеется в библиотеках си.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
07.02.2013, 00:50     Все возможные перестановки элементов заданного массива #18
Цитата Сообщение от palva Посмотреть сообщение
Я думаю, что если задача учебная
Тогда ее надо решать а не на форум постить!
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 01:21     Все возможные перестановки элементов заданного массива #19
Цитата Сообщение от Dr.Urban Посмотреть сообщение
Тогда ее надо решать а не на форум постить!
Вы как всегда правы. Чтобы возместить автору тот вред, который я ему нанес, выложив свой код, предложу ему изучить статью, которая объясняет алгоритм. http://window.edu.ru/resource/334/24.../2003_2_84.pdf
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2013, 04:25     Все возможные перестановки элементов заданного массива
Еще ссылки по теме:

Вывести на экран все возможные перестановки введенных символов. Где ошибка? C++
C++ Вывести все возможные перестановки слов в предложении
C++ Рекурсивная функция: все возможные перестановки символов строки

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
07.02.2013, 04:25     Все возможные перестановки элементов заданного массива #20
Цитата Сообщение от palva Посмотреть сообщение
Вы как всегда правы. Чтобы возместить автору тот вред, который я ему нанес, выложив свой код, предложу ему изучить статью, которая объясняет алгоритм. http://window.edu.ru/resource/334/24.../2003_2_84.pdf
кстати, спасибо, отличная статья!
Yandex
Объявления
07.02.2013, 04:25     Все возможные перестановки элементов заданного массива
Ответ Создать тему
Опции темы

Текущее время: 02:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru