C++ std::next_permutation 順列が期待通りに作成されない

###知りたいこと
std::next_permutationの使い方が間違っているのかも知れません。
いわゆる順列のみのリストが欲しいです。
サンプルコードのどこに問題があるのかご教示頂けると助かります。

###現状
std::next_permutationで順列を作成すると引数のリストの中から各要素を1回づつ使ったものが生成されるはずなのですが、何故か同じ要素が何度も使われたリストが出来てしまいます。
このリストを使った問題を解きたいのですがこのリストが間違っているので躓いてしまっています。

###試したこと
デバッグでvector配列の中身を少しだけ出力などして確認するとやはりおかしな数値が紛れていました。

###サンプルコード
質問用に最低限の部分のみ抜粋

C++
1#include <cstdio>
2#include <iostream>
3#include <iterator>
4#include <algorithm>
5#include <vector>
6
7//順列リストから数値に変換
8unsigned get_pd(const std::vector<unsigned> &v)
9{
10    unsigned result = 0;
11    for (auto x : v)
12    {
13        result = 10 * result + x;
14    }
15    return result;
16}
17
18void qa_test()
19{
20    //順列リスト作成
21    std::vector<unsigned> vpd({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
22    std::vector<unsigned> vpds;
23    do
24    {
25        vpds.push_back(get_pd(vpd));
26    } while (std::next_permutation(vpd.begin(), vpd.end()));
27
28    //少しだけ中身の確認
29    unsigned count = 0;
30    for (auto x : vpds)
31    {
32        ++count;
33
34        //問題のある数値の位置を確認
35        // if (x == 1168105595)
36        // {
37        //     std::cout << count << std::endl;
38        //     break;
39        // }
40
41        //最初の一部を出力
42        if (count > 0 && count < 10)
43        {
44            std::cout << x << std::endl;
45        }
46
47        //問題のある数値の一部を出力
48        if (count > 1998050)
49        {
50            std::cout << x << std::endl;
51        }
52
53        if (count > 1998060)
54        {
55            break;
56        }
57    }
58    std::cout << std::endl;
59
60    return;
61}
62
63int main()
64{
65    qa_test();
66    getchar();
67    return 0;
68}
69

//配列の最初の一部を出力
123456789
123456798
123456879
123456897
123456978
123456987
123457689
123457698
123457869

//問題のある数値の一部を出力
1168104533
1168104596
1168104632
1168104686
1168104893
1168104902
1168105523
1168105595
1168105622
1168105685
1168110833

行動規範の内容に同意します

回答1件

自己解決

3箇所ほどunsigned long long に変更すると正常動作しました。
サンプルで見ていた桁がちょうど回答に近い桁で盲点でした。
型の限界を超えた値が予期しない値になっていたようです。

std::vector<unsigned long long> vpds;
unsigned long long get_pd(const std::vector<unsigned> &v)
unsigned long long result = 0;

c++
1#include <cstdio>
2#include <iostream>
3#include <iterator>
4#include <algorithm>
5#include <vector>
6#include <cmath>
7
8//順列リストから数値に変換
9unsigned long long get_pd(const std::vector<unsigned> &v)
10{
11    unsigned long long result = 0;
12    for (auto x : v)
13    {
14        result = 10 * result + x;
15    }
16    return result;
17}
18
19void qa_155986()
20{
21    //順列リスト作成
22    std::vector<unsigned> vpd({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
23    std::vector<unsigned long long> vpds;
24    do
25    {
26        vpds.push_back(get_pd(vpd));
27    } while (std::next_permutation(vpd.begin(), vpd.end()));
28
29    //少しだけ中身の確認
30    unsigned count = 0;
31    for (auto x : vpds)
32    {
33        ++count;
34
35        //問題のある数値の位置を確認
36        // if (x == 1168105595)
37        // {
38        //     std::cout << count << std::endl;
39        //     break;
40        // }
41
42        //最初の一部を出力
43        if (count > 0 && count < 10)
44        {
45            std::cout << x << std::endl;
46        }
47
48        //問題のある数値の一部を出力
49        if (count > 1998050)
50        {
51            std::cout << x << std::endl;
52        }
53
54        if (count > 1998060)
55        {
56            break;
57        }
58    }
59    std::cout << std::endl;
60
61    return;
62}
63
64int main()
65{
66    qa_155986();
67    getchar();
68    return 0;
69}
70

投稿2018/11/03 13:32

opyon

総合スコア1009