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

Перестановки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 22:12     Перестановки #1
Даны символы, например ABCDEF, и число n. Нужно вывести все возможные комбинации перестановок этих символов по n. Максимальное число комбинаций будет равно 6^n. Как реализовать алгоритм. Какой час бьюсь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2013, 22:12     Перестановки
Посмотрите здесь:

C++ перестановки в С++
Перестановки C++
C++ Сдвиг перестановки.
Инверсии и перестановки C++
C++ те же перестановки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
17.10.2013, 22:29     Перестановки #2
я мб ошибаюсь, но по-моему максимально возможное число перестановок будет n=6! (факториал).
А вот как сделать, не знаю, надо подумать) ...была мысль сделать функцию которая возвращает ссылку и принимает 2 ссылки на 2 элемента, меняя их значения местами, ну и как нить рекурсивно это заделать

Не по теме:

спасибо теперь я не усну)

SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 22:38  [ТС]     Перестановки #3
Нет. Как раз таки 6^n.
Возмьем не 6 символов, а 2 (AB) и n = 3. Т.е. всего комбинаций 2^3=8:
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
17.10.2013, 22:38     Перестановки #4
можно типа функцию с 1 циклом, которая меняет местами *А с остальными, а потом в этой функции вызвать себя же но *(А+1) и так далее...
Убежденный
Системный программист
 Аватар для Убежденный
14217 / 6232 / 988
Регистрация: 02.05.2013
Сообщений: 10,390
Завершенные тесты: 1
17.10.2013, 22:40     Перестановки #5
Если все-таки перестановки, тогда подойдет std::next_permutation.
И не надо ничего реализовывать.
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
17.10.2013, 22:45     Перестановки #6
то что ты сделал это выборка вроде...яне помню, надо почитать))
для АBC:
ABC 1
АСВ 2
ВСА 3
ВАС 4
CAB 5
CBA 6

Статистика. Теория вероятностей

почитай теорвер про перестановки
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 22:57  [ТС]     Перестановки #7
В моем случае символы в строке могут повторяться. Для ABC:
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC

Добавлено через 6 минут
То есть размещения с повторениями.
-=ЮрА=-
Заблокирован
Автор FAQ
17.10.2013, 23:11     Перестановки #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main()
{
    int i, j, k, n;
    const char data[] = "ABCDEF";
    n = sizeof(data) / sizeof(data[0]) - 1;
    for( i = 0; i < n; i++ )
    for( j = 0; j < n; j++ )
    for( k = 0; k < n; k++ )
        cout<<data[i]<<data[j]<<data[k]<<endl;
    cin.get();
    return 0;
}
Вывод
AAA
AAB
AAC
AAD
AAE
AAF
ABA
ABB
ABC
ABD
ABE
ABF
ACA
ACB
ACC
ACD
ACE
ACF
ADA
ADB
ADC
ADD
ADE
ADF...
http://codepad.org/u6xSdFEl
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
17.10.2013, 23:19     Перестановки #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
#include <iostream>
#include <clocale>
#include <algorithm>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    // sort(A, A + N); // необходимо при вводе произвольных элементов
    do
    {
        for (int i=0; i < N; i++)
            cout << A[i] << ' ';
        cout << endl;
        counter++;
    } while (next_permutation(A, A + N));
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <clocale>
 
using namespace std;
 
// вывод множества на экран
void print(const int *A, const int size);
// функция перестановки двух чисел
void swap(int &, int &);
// функция генерации следующей перестановки
void next_perm(int k, int *A, const int size, int &counter);
 
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    next_perm(0, A, N, counter);
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
 
void print(const int *A, const int size)
{
    for (int i=0; i < size; i++)
        cout << A[i] << ' ';
    cout << endl;
}
 
void swap(int &x, int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
 
void next_perm(int k, int *A, const int size, int &counter)
{
    // если заполнилось
    if (k == size)
    {
        print(A, size);
        counter++;
        return;
    }
 
    for(int i = k; i < size; i++)
    {
        swap(A[k], A[i]);
        next_perm(k + 1, A, size, counter); // следующая перестановка
        swap(A[k], A[i]);
    }
}
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 23:24  [ТС]     Перестановки #10
-=ЮрА=-, спасибо, но всегда размещает по 3. Как исправить, чтобы размещал по нужному количеству?
-=ЮрА=-
Заблокирован
Автор FAQ
17.10.2013, 23:31     Перестановки #11
Цитата Сообщение от SDmaN Посмотреть сообщение
Как исправить, чтобы размещал по нужному количеству?
- сколько надо за раз элементов - столкьо и вложенных циклов, скажем если надо 5 элементов то надо ввести +2 цикла ниже цикла по к
Убежденный
Системный программист
 Аватар для Убежденный
14217 / 6232 / 988
Регистрация: 02.05.2013
Сообщений: 10,390
Завершенные тесты: 1
17.10.2013, 23:36     Перестановки #12
Ок, раз пошла такая пьянка, моя версия

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <string.h>
#include <iostream>
 
 
 
namespace
{
 
 
 
void show_state(char const *pCharset, size_t const *pState, size_t StateSize)
{
    for (size_t i = 0; i < StateSize; ++i)
    {
        std::cout << pCharset[pState[i]];
    }
 
    std::cout << std::endl;
}
 
 
 
bool increment_state(size_t *pState, size_t StateSize)
{
    for (size_t i = 0; i < StateSize; ++i)
    {
        if (++pState[i] < StateSize)
        {
            return true;
        }
 
        pState[i] = 0;
    }
 
    return false;
}
 
 
 
} // namespace
 
 
 
int main()
{
    char const *pCharset = "ABC";
 
    size_t const StateSize = strlen(pCharset);
    size_t *pState = new size_t[StateSize];
    memset(pState, 0, StateSize * sizeof (size_t));
 
    do
    {
        show_state(pCharset, pState, StateSize);
    } while (false != increment_state(pState, StateSize));
 
    delete [] pState;
 
    return 0;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
17.10.2013, 23:37     Перестановки #13
SDmaN, у меня код для любого количества (задается константой), надо лишь поменять массив на символьный и заполнить его значениями
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 23:39  [ТС]     Перестановки #14
MrGluck, ваш код - перестановки, мне нужны размещения. Извините, тему неправильно назвал.
Убежденный
Системный программист
 Аватар для Убежденный
14217 / 6232 / 988
Регистрация: 02.05.2013
Сообщений: 10,390
Завершенные тесты: 1
17.10.2013, 23:48     Перестановки #15
Цитата Сообщение от SDmaN Посмотреть сообщение
Нужно вывести все возможные комбинации перестановок этих символов по n.
А, извиняюсь, неправильно прочитал условие темы.
Исправленный вариант:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <string.h>
#include <iostream>
 
 
 
namespace
{
 
 
 
void show_state(char const *pCharset, size_t const *pState, size_t Count)
{
    for (size_t i = 0; i < Count; ++i)
    {
        std::cout << pCharset[pState[i]];
    }
 
    std::cout << std::endl;
}
 
 
 
bool increment_state(size_t *pState, size_t CharsetSize, size_t Count)
{
    for (size_t i = 0; i < Count; ++i)
    {
        if (++pState[i] < CharsetSize)
        {
            return true;
        }
 
        pState[i] = 0;
    }
 
    return false;
}
 
 
 
} // namespace
 
 
 
int main()
{
    // ---------------------------
    //
    // Входные данные.
 
    char const *pCharset = "AB";
    size_t const Count   = 3;
 
    // ----------------------------
 
    size_t const CharsetSize = strlen(pCharset);
    size_t *pState = new size_t[Count];
    memset(pState, 0, Count * sizeof (size_t));
 
    do
    {
        show_state(pCharset, pState, Count);
    } while (false != increment_state(pState, CharsetSize, Count));
 
    delete [] pState;
 
    return 0;
}
Вывод:
AAA
BAA
ABA
BBA
AAB
BAB
ABB
BBB
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.10.2013, 23:50     Перестановки
Еще ссылки по теме:

перестановки с повторениями! C++
C++ Номер перестановки
C++ Перестановки с next_permutation

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
17.10.2013, 23:50     Перестановки #16
Эх, где-то был вариантик, попробую в недавних сообщениях поискать.
Пока вот, пример
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 2
 
class Alphabet
{
    int tick[N];
    std::vector<char> all;
    bool stop;
  public:
    Alphabet();
    void entry(std::string, std::ostream &);
    Alphabet& operator ++();
    bool isStop() {return stop; }
};  
 
unsigned long countEntry(const std::string &, const std::string &);
 
int main()
{
    std::ifstream ifstext("text2.txt");
    std::ofstream o("result.csv");
    if(!ifstext)
    {
        std::cout<< "No file\n";
        return 1;
    }
    std::string text;
    ifstext >> std::noskipws; // clears the scipws flag for the str stream
    std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), std::back_inserter(text));
    Alphabet a;
    std::cout<< "Please wait"<< std::endl;
    while (!a.isStop())
        (++a).entry(text, o);
    return 0;
}
 
unsigned long countEntry(const std::string &s, const std::string &delim)
{
    unsigned long counter = 0, found = s.find(delim); // found - number, where we start finding
    if (found != std::string::npos) counter++; // if in first position
    while(true)
    {
        found = s.find(delim, found + 1);
        if (found != std::string::npos) counter++;
        else break;
    }
    return counter;
}   
 
Alphabet::Alphabet()
{
    stop = false;
    for (int i=0; i < N; i++) 
        tick[i] = -1;
    for (int i=0x03E1; i < 0x03FA; i++)
        all.push_back( char(i) );
}
 
void Alphabet::entry(std::string text, std::ostream &o)
{
    if (stop) return;
    std::string str;
    for (int i=0; i < N; i++)
        if (tick[i] != -1)
           str.push_back( all[ tick[i] ] );
    o<< str<< ", "<< countEntry(text, str)<< std::endl;
}
 
Alphabet& Alphabet::operator ++()
{
    tick[N-1]++;
    for (int i = N-1; i > 0; i--) 
    if (tick[i] == all.size())
    {
        /*if (i == 1) // show new procent
        {
            std::cout<< "|";
            std::cout.flush(); // output stream buffer
        }*/
        tick[i - 1]++;
        tick[i] -= all.size();
    }
    if (tick[0] == all.size())
        stop = true;
    return *this;
}
Тут брало и искало все размещения для греческого алфавита. Количество символов - также N.
Второй вариант выполнения этого же задания:
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
struct comp // comparison in map
{
    bool operator()(const std::string &str1, const std::string &str2) const
    {
        return (str1.length() == str2.length() ? str1 < str2 : str1.length() < str2.length() );
    }
};
 
typedef std::map <std::string, unsigned int, comp> map_string_uint;
 
class Combinations
{
    map_string_uint allcomb;
    std::vector<char> alphabet;
  public:
    Combinations();
    void entry(const std::string &);
    void print(std::ostream &);
};
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    if (!ifstext)
    {
        std::cerr<< "No file\n";
        return 1;
    }
    std::string text;
    ifstext >> std::noskipws; // clears the scipws flag for the str stream
    std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), 
          std::back_inserter(text) );
    std::cout<< "Text downloaded in buffer"<< std::endl;
    Combinations c;
    std::cout<< "Combinations compiled"<< std::endl;
    c.entry(text);
    std::cout<< "Writing results in file"<< std::endl;
    c.print(o);
    std::cout<< "Completed"<< std::endl;
    return 0;
}
 
Combinations::Combinations()
{
    for (int i=0x03E1; i < 0x03FA; i++) // forming alphabet
        alphabet.push_back( char(i) );
    int tick[N];
    std::fill(tick, tick + N-1, -1);
    tick[N-1] = 0;
    std::string str;
    while (tick[0] != alphabet.size())
    {
        // forming new combination
        str.clear();
        for (int i=0; i < N; i++)
            if (tick[i] != -1)
                str.push_back( alphabet[ tick[i] ] );
        allcomb.insert( std::make_pair(str, 0) );
        tick[N-1]++; // incriminating combination
        for (int i=N-1; i > 0; i--) // if need increase capacity (разрядность)
            if (tick[i] == alphabet.size())
            {
                tick[i - 1]++;
                tick[i] -= alphabet.size();
            }
    }
}
 
void Combinations::entry(const std::string &text)
{
    std::string buf;
    for (int i=0; i < text.length(); i++)
    {
        for (int j=0; j < N && i + j < text.length(); j++)
        {
            if (std::binary_search (alphabet.begin(), alphabet.end(), text[i + j]) )
            {
                buf.push_back( text[i + j] );
                ++allcomb[buf]; // incriminating counter
            }
            else break;
        }
        buf.clear();
    }
}                
 
void Combinations::print(std::ostream &o)
{
    std::for_each(allcomb.begin(), allcomb.end(), [&o](const std::pair <std::string, int> &p)
        { o<< p.first<< ", "<< p.second<< std::endl; } );
}
Думаю поможет
Yandex
Объявления
17.10.2013, 23:50     Перестановки
Ответ Создать тему
Опции темы

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