組み合わせと順列 アルゴリズム

質問

こんにちは
組み合わせと順列についてです。
順序関係のある要素で構成される集合から一定の数をとり、順列を辞書順で生成する方法がわかりません。
うまく説明できないので、例を示します。

たとえば２６文字のアルファベットから４文字を選んで辞書順に生成するプログラムはどのようにやればいいのでしょうか？
このアルファベットの例だと
abcd
abce
abcf
・・・
abcz
abdc
abde
・・・
zyxw

のようになると思います。
要素と長さが決まっている場合で順列を生成する部分は大丈夫です。（C++　STLのnext_permutationにあたる部分)
一応自分なりに考えたやり方は２６進数４桁のように考えて、それを１ずつ増やし、全体で２回以上使われていないかを調べる　と思ったんですが、あまりスマートじゃないし要素がとびとびのアルファベットのときなどに応用が利かないと思いました。
指摘していただければ補足しますので、よろしくお願いします。

回答No.4

επιστημη（@episteme） · ベストアンサー

これでどうだ。

#include <iostream>
#include <string>
#include <array>
#include <algorithm>

using namespace std;

// nPr : 13枚のカードから5枚選んで並べる
int main() {
const int N = 13;
const int R = 5;
string rank = "23456789TJQKA";

// select = { -1, -1, ... -1, 0, 1, 2, 3, 4 }
array<int,N> select;
fill(select.begin(), select.end(), -1);
iota(select.end()-R, select.end(), 0);

int perm = 0;
do {
++perm;
string result(R,' ');
for ( int i = 0; i < N; ++i ) {
if ( select[i] >= 0 ) result[select[i]] = rank[i];
}
cout << result << endl;
} while ( next_permutation(select.begin(), select.end()) );
cout << perm << endl;
}

お礼

回答ありがとうございます。
こんなやり方もあるんですね。
さっきのでも工夫すればできたと思いますけどこれだと一部かえるだけで使いまわせますね。
とても参考になりました！
本当にありがとうございました。

回答No.3

gerugugu84

#define ALPHABET_NUM 4
にしたら４文字になります。

回答No.2

gerugugu84

＃１の方法だと左側のアルファベットより若い文字は出力されないのでは？
つまり質問者の例にあるような
"abdc"
や
"zyxw"
といった文字列は出力されないはず。

とりあえずあまりスマートなコードではないけどどうぞ。

#include <stdio.h>

#define ALPHABET_NUM 2

static char buffer[ ALPHABET_NUM + 1 ];

void permutate( unsigned int alpha, int depth )
{
if( ALPHABET_NUM <= depth )
{
buffer[ depth ] = '\0';
printf( "%s\n", buffer );
return;
}

unsigned int mask = 1;
for( int bit = 0; bit < 26; bit++ )
{
if( alpha & mask )
{
buffer[ depth ] = 'a' + bit;
permutate( alpha ^ mask, depth + 1 );
}
mask = mask << 1;
}
}

int main()
{
unsigned int alpha = 0x3FFFFFF;
permutate( alpha, 0 );
return 0;
}

お礼

なるほど！
完璧ですね！
確かにこういう全探索かけば辞書順になりますね。
排他的論理輪でビット落としたりしてるのも参考になります。
本当にありがとうございました。

補足

＃１さんのもさらにnext_permutationを使うことでできるのであっていると思います。

回答No.1

επιστημη（@episteme）

next_permutationで26個から4個えらびだしてみた。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
string alpha = "abcdefghijklmnopqrstuvwxyz";
string digit = "00000000000000000000001111";
do {
string result;
for ( string::size_type i = 0; i < digit.size(); ++i ) {
if ( digit[i] == '1' ) result += alpha[i];
}
cout << result << endl;
} while ( next_permutation(digit.begin(), digit.end()) );
}

あとは result をnext_permutationで並び替えればいんじゃないかと。

お礼

回答ありがとうございます。
これだとコードが短い上にわかりやすくていいですね。
next_permutationの使い方がとても勉強になりました。
本当にありがとうございました。