質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.58%

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,166

opyon

score 991

知りたいこと

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

現状

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

試したこと

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

サンプルコード

質問用に最低限の部分のみ抜粋

#include <cstdio>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

//順列リストから数値に変換
unsigned get_pd(const std::vector<unsigned> &v)
{
    unsigned result = 0;
    for (auto x : v)
    {
        result = 10 * result + x;
    }
    return result;
}

void qa_test()
{
    //順列リスト作成
    std::vector<unsigned> vpd({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
    std::vector<unsigned> vpds;
    do
    {
        vpds.push_back(get_pd(vpd));
    } while (std::next_permutation(vpd.begin(), vpd.end()));

    //少しだけ中身の確認
    unsigned count = 0;
    for (auto x : vpds)
    {
        ++count;

        //問題のある数値の位置を確認
        // if (x == 1168105595)
        // {
        //     std::cout << count << std::endl;
        //     break;
        // }

        //最初の一部を出力
        if (count > 0 && count < 10)
        {
            std::cout << x << std::endl;
        }

        //問題のある数値の一部を出力
        if (count > 1998050)
        {
            std::cout << x << std::endl;
        }

        if (count > 1998060)
        {
            break;
        }
    }
    std::cout << std::endl;

    return;
}

int main()
{
    qa_test();
    getchar();
    return 0;
}
//配列の最初の一部を出力
123456789
123456798
123456879
123456897
123456978
123456987
123457689
123457698
123457869

//問題のある数値の一部を出力
1168104533
1168104596
1168104632
1168104686
1168104893
1168104902
1168105523
1168105595
1168105622
1168105685
1168110833
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

check解決した方法

0

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;

#include <cstdio>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cmath>

//順列リストから数値に変換
unsigned long long get_pd(const std::vector<unsigned> &v)
{
    unsigned long long result = 0;
    for (auto x : v)
    {
        result = 10 * result + x;
    }
    return result;
}

void qa_155986()
{
    //順列リスト作成
    std::vector<unsigned> vpd({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
    std::vector<unsigned long long> vpds;
    do
    {
        vpds.push_back(get_pd(vpd));
    } while (std::next_permutation(vpd.begin(), vpd.end()));

    //少しだけ中身の確認
    unsigned count = 0;
    for (auto x : vpds)
    {
        ++count;

        //問題のある数値の位置を確認
        // if (x == 1168105595)
        // {
        //     std::cout << count << std::endl;
        //     break;
        // }

        //最初の一部を出力
        if (count > 0 && count < 10)
        {
            std::cout << x << std::endl;
        }

        //問題のある数値の一部を出力
        if (count > 1998050)
        {
            std::cout << x << std::endl;
        }

        if (count > 1998060)
        {
            break;
        }
    }
    std::cout << std::endl;

    return;
}

int main()
{
    qa_155986();
    getchar();
    return 0;
}
123456789
123456798
123456879
123456897
123456978
123456987
123457689
123457698
123457869

5463071829
5463071892
5463071928
5463071982
5463072189
5463072198
5463072819
5463072891
5463072918
5463072981
5463078129

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.58%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る