順列文字の生成処理

質問

次のような左端の番号に対応した右側の文字列を作りたいのです。
これらの４個の文字列は、重複無しの順列になります。
下表では文字列が４個ですが、実際には７個程度まで生成したいのです。７個の場合は合計1*2*3*4*5*6*7=5040個になります。
言語はFORTRANですがＣでも、あるいは手順説明でも良いです。文字列でなくともn桁数字あるいは配列でも良いです。c＋＋のクラス処理も候補かも知れませんが、FORTRANで書くには荷が重いです。再帰処理は何とかなるかも知れませんが、できれば無しを希望します。
４個程度ならデータとして書けば済みますが、６，７個となるとそうは行きませんので、プログラムで生成したいのです。処理時間は問題になりません。
Ｎ個の処理を使ってn+1個の処理の形式で大分頭を悩ませましたが、ギブアップ気味です（まだ1日程度ですが）。虫の良いお願いですが奇特な諸兄のお知恵を拝借したく存じます。

1: 1234
2: 2134
3: 1324
4: 3124
5: 2314
6: 3214

7: 1243
8: 2143
9: 1423
10: 4123
11: 2413
12: 4213

13: 1342
.
.
18: 4312

19: 2341
.
.
24: 4321

回答No.11

f272 · ベストアンサー

#4 ＆ #5 ＆ #9です。
逆の手続きも欲しがっているようなので，fortranで作ってみた。ついでに以前のコードも手直ししてある。しかし本質的には以前のコードと何も変わっていません。一応n=4のときに全ケースで，場合番号から組み合わせ文字列を作り，さらにその組み合わせ文字列から場合番号を再計算するようになっています。当然ですが，最初の場合番号と同じものが返されます。

program main
implicit none
integer::n,nt,nt1,np
integer,allocatable,dimension(:)::nn
integer,allocatable,dimension(:)::pp
n=4
allocate(nn(n-1))
allocate(pp(n))
np=factorial(n)

do nt=1,np
call n2f(nt,n,nn)
Call f2p(n,nn,pp)
call p2f(n,nn,pp)
nt1=f2n(n,nn)
print*,nt,":",pp,":",nt1
end do

contains

integer function factorial(n)
integer::n
integer::n1
factorial=1
n1=n
do
factorial=factorial*n1
n1=n1-1
if (n1==1) exit
end do
end function

subroutine p2f(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,i2,c
do i=1,n-1
c=0
do i2=1,i
if(pp(i2)>pp(i+1))c=c+1
end do
nn(i)=c
end do
end subroutine

integer function f2n(n,nn)
integer::n
integer,dimension(*)::nn
integer::i,n1
n1=n
f2n=0
do i=1,n-1
f2n=(f2n*n1)+nn(n-i)
n1=n1-1
end do
f2n=f2n+1
end function

subroutine n2f(nt,n,nn)
integer::nt,n
integer,dimension(*)::nn
integer::i,nt1
nt1=nt-1
do i=1,n-1
nn(i)=mod(nt1,i+1)
nt1=int(nt1/(i+1))
end do
end subroutine

subroutine f2p(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,j,j2,t
do i=1,n
pp(i)=i
end do
do i=n-1,1,-1
j=nn(i)
t=pp(i+1-j)
do j2=i+1-j,i
pp(j2)=pp(j2+1)
end do
pp(i+1)=t
end do
end subroutine
end program

お礼

逆の手続きまでFORTRANでご教示頂き大変ありがとうございます。
効果を確認の上、結果をこの回答番号の補足コメントで後程報告させていただきます。
とりあえずお礼まで。

補足

実装する時間がとれましたので、現方法（no1さんの改善ベース）とこのno.11さんの新方法とを比較検証しました。
分析したい事象データ数は１５０万個ほどで、文字列の並び（次元）の数を５個と６個で実行しました。結果は同じでしたので正しく実装されています。
６個の場合の実行時間
現方法　８’５１”　新方法　９’１４”　
５個の場合（６個とは試す数が少ないですが、比較には問題ないです）
現方法　４’３５”　新方法　３’４３”
となって、次元数が６個と大きいと現方法が有利、５個と少ないと新方法有利です。
実装方法には大きな違いがあって、現方法ではパターン（並びの種類数、６個で７２０個）用のテーブルを大量に用意しなければなりませんが、新方法では不要な効果があります。これは実装上のかなりの制約になっています。
今後はケースによってつかいわけることになろうかと思っています。
順方向と逆方向まで完全なソースをご教示頂きありがとうございました。

回答No.10

HohoPapa

>追加
>ただ期待の文字列かは、
>0+1+2+3+4+5+6ではだめで、全ての文字列がそろっているかになるはずです

コードをよく見ていただきたいのですが．．．
篩を２段階にすることで高速化を目指しています。

つまり
>・７つの文字列の合計が0+1+2+3+4+5+6 か？
これを満足していなかったらFalse("NG")とすることで、
より早く判定ルーチンから抜け
満足していたら、続いて
>・0,1,2,3,4,5,6の文字列があるか？
をチェックしています。

お礼

なるほど、そうでしたか。コード見てそれのようにわかりました。
このふるいの効果は、すべての文字がそろっているかの判定をスキップできることなのですね。
ただＮo1さんの方法では７重ループの外側の方からふるいにかける工夫ができますので、そちらの方が期待文字列かどうかの判定回数は少なくなるように思います。
話題がそれますが、Ｎo8さんへのお礼に述べていますが、
組わ合わせ文字列から、場合番号への変換と、場合番号から組み合わせ文字列への変換の2種類のニーズがあって、最初の質問では後者のことについてでした。ご提案頂いた頂いた方法は、すべての組み合わせ文字列を順番に生成する方法に関することで、これを前者に適用するためには、指定の文字列を組み合わせ文字列テーブルから検索することになります（現実装）。
現実装では速度的、サイズ上で少々不満なので改善方法を模索しています。

回答No.9

f272

#4 ＆ #5です。
fortranが好きそうなので，fortranで同じプログラムを書いてみた。
なお，#4でのEnd Subの直前のNextは単なる消し忘れです。

program main
implicit none
integer::k,n,np,nt,nt1
integer,allocatable,dimension(:)::nn
integer,allocatable,dimension(:)::pp
n=7
allocate(nn(n-1))
allocate(pp(n))
np=factorial(n)
do nt=0,np-1
nt1=np-1-nt
Call n2f(nt1,n,nn)
Call f2p(n,nn,pp)
print*,nt+1,": ",pp
end do
contains
integer function factorial(n)
integer::n
integer::n1
factorial=1
n1=n
do
factorial=factorial*n1
n1=n1-1
if (n1==1) exit
end do
end function
subroutine n2f(nt1,n,nn)
integer::nt1,n
integer,dimension(*)::nn
integer::i
do i=1,n-1
nn(i)=0
end do
k=1
Do
k=k+1
nn(n-k+1)=mod(nt1,k)
nt1=int(nt1/k)
if (nt1<=0) exit
end do
end subroutine
subroutine f2p(n,nn,pp)
integer::n
integer,dimension(*)::nn,pp
integer::i,j,j2,k2,t
do i=1,n
pp(n+1-i)=i
end do
k=n-1
k2=n-1
do i=1,k
j=nn(i)
t=pp(k2+1-j)
do j2=k2+1-j,k2
pp(j2)=pp(j2+1)
end do
pp(k2+1)=t
k2=k2-1
end do
end subroutine
end program

お礼

FORTRANのコードで例示頂きありがとうございます。これならスムーズに確認することができそうです。

補足

今コードをコピペしてGFORTRANで実行するとなんのエラーもなく５０４０個の組み合わせがPRINTされました。コードの完成度と移行性が素晴らしいです。普段使わない記述があるのに！！
動作を読んでみます。
（送れるチップの数が残りわずかになりました）

回答No.8

superside0

N枚のカードを並べるときの　順列・組み合わせの数はN! (Nの階乗）　ですが
その　1～N!の番号のうち　任意の番号を指定したら、
使わない値も埋めてあるテーブル（配列）を事前に作ることなく、
計算一発でその値を取り出せるような、便利な関数はないものか
ということですよね。
（重複ありだと簡単ですけど、重複なしの値だと直線的に並ばないので
　ループなしの計算で出すのは、難しそうな感じですね。
　N番目の素数を求めることがループなしの計算ではできなので、
　暗号が破り難いのと似てるような感じなのかも。）

用途次第だとは思いますが、
もし、番号を指定して同じ番号で同じ結果である必要がなく
N桁の重複なしのランダムな値を生成するだけでいいなら
・ランダム関数をマイクロ秒等を使って同じ初期値にならないようにしておく
・1～Nの値の入ったN個の配列からランダムに１つ選ぶ
・配列から上の数値を取り除いて、N-1個からランダムに１つ選ぶ
・上を1個になるまで繰り返す
とすれば、N回の計算で終わりますが、
用途として合わないのでしょうね。

お礼

最初の質問はその通りです。
やはり直線的に並ばないので難しいわけですね。この直線的に並ばないという表現がなるほどです。
後段のご提案は合わないですね。

その後、no1さんの方法でテーブルをつくり、それを検索する方法（検索の必要性はまだ説明してないですが）で、目的の検証を進めましたが、やはりこの方法では時間がかかることがわかりました。桁数は７桁もいらず、５－６桁程度になっています。
最初の質問は、組み合わせ総数の中の番号から、対応する組み合わせを求めることでしたが、前段階として、組み合わせの一つが与えられて、それに対応する組み合わせ総数の内の一つの番号をつくることも必要で、時間メモリ制約は後者の方です。この方法についても未解決ですが、別途質問項目を挙げてみたいと思います。その際はよろしく。

回答No.7

HohoPapa

こんなアイデアはいかがでしょうか？

７桁を例に説明します。
７進数で　0000000　～　6666666 までの文字列を組立
総当たりで、期待の文字列かどうかをチェックし
期待の文字列だけを書き出します。

期待の文字列かどうかは
・７つの文字列の合計が0+1+2+3+4+5+6 か？
・0,1,2,3,4,5,6の文字列があるか？
でチェックします。

以下、VBAのサンプルです。

なお、
総当たりの範囲を
７進数で　0000000　～　6666666
ではなく、
７進数で　0123456　～　6543210
とすれば、若干性能を改善できるかもしれません。

Option Explicit

Sub Test2()
　Dim wkC As Long
　Dim MyCode As String
　Dim HitCount As Long
　HitCount = 0
　'For wkC = 0 To 7 ^ 7
　For wkC = 22875 To 800667
　　MyCode = Get7Code(wkC)
　　If MyCode <> "NG" Then
　　　HitCount = HitCount + 1
　　　ThisWorkbook.Sheets(1).Cells(HitCount, 1).Value = "'" & MyCode
　　End If
　Next wkC
End Sub

Function Get7Code(Myi As Long) As String

　Dim wki(7) As Long
　Dim wkT As String
　Dim i As Long

　i = Myi

　wki(7) = i \ (7 ^ 6)
　i = i - wki(7) * (7 ^ 6)
　wki(6) = i \ (7 ^ 5)
　i = i - wki(6) * (7 ^ 5)
　wki(5) = i \ (7 ^ 4)
　i = i - wki(5) * (7 ^ 4)
　wki(4) = i \ (7 ^ 3)
　i = i - wki(4) * (7 ^ 3)
　wki(3) = i \ (7 ^ 2)
　i = i - wki(3) * (7 ^ 2)
　wki(2) = i \ (7 ^ 1)
　i = i - wki(2) * (7 ^ 1)
　wki(1) = i \ (7 ^ 0)

　Get7Code = "NG"

　If wki(7) + wki(6) + wki(5) + wki(4) + wki(3) + wki(2) + wki(1) <> 0 + 1 + 2 + 3 + 4 + 5 + 6 Then
　　 Exit Function
　End If

　wkT = _
　　Format(wki(7), "0") & _
　　Format(wki(6), "0") & _
　　Format(wki(5), "0") & _
　　Format(wki(4), "0") & _
　　Format(wki(3), "0") & _
　　Format(wki(2), "0") & _
　　Format(wki(1), "0")

　If InStr(wkT, "0") = 0 Then Exit Function
　If InStr(wkT, "1") = 0 Then Exit Function
　If InStr(wkT, "2") = 0 Then Exit Function
　If InStr(wkT, "3") = 0 Then Exit Function
　If InStr(wkT, "4") = 0 Then Exit Function
　If InStr(wkT, "5") = 0 Then Exit Function
　If InStr(wkT, "6") = 0 Then Exit Function

　Get7Code = wkT
End Function

お礼

度重ねてコードのご教示ありがとうございます。
この方法は、no1さんの方法と似ていますね。それでは、重複数字があればその組わせは除く点が異なります。現在この方法でやっています。
それからno8さんへのお礼も見て頂けると幸いです。
追加
ただ期待の文字列かは、0+1+2+3+4+5+6ではだめで、全ての文字列がそろっているかになるはずです。

回答No.6

m-take0220

速度が問題になるのであれば、数列と番号の対応をとるのではなく、数列をそのまま数値として使用してはいかがでしょうか?
数列の長さが7であれば800万個の配列を用意すれば全て収まります。
(厳密には7,654,321個で十分ですが)
今のPCなら、整数800万個のデータを保持するだけのメモリは余裕で持っています。1データ4バイトとしても、32MB程度ですから。

お礼

ご返事ありがとうございます
その通りで非常に簡明になるので悩んでいるときはそれも考えましたが、最終的には同じPC上ではあるが、多分メモリ制約の多いインタープリタ言語のプラットフォームで処理せねばならないので、いかにも無駄のある処理には踏み切れておりません。
現在はNO1さんの簡明な方法でコーディングして進めています。しかし検証が進み速度の向上の必要性の段階になれば、その方法なども候補になるだろうと考えています。

補足

この方法も速度改善のために少し考えましたが、
実は８００万個なりの配列は一つだけではなく、数十万個必要なことに気が付きました。メモリはオーバしてしまい、切り詰めてもテーブルサイズの上限は数万程度のようです。

回答No.5

f272

#4です。

> なにかうまく番号から数列を計算できないかが質問でした。

そうなるように作ったのに，わかってくれなくて悲しいです。

Sub main()
Dim k As Long
Dim n As Long
Dim np As Long, nt As Long, nt1 As Long
n = 4 '4個の文字列ならば4とする
ReDim nn(1 To n - 1) As Long
ReDim pp(1 To n) As Long
np = 24 '4個の文字列ならば4!=24とする
nt = 6 '左端の番号が7ならば1を引いて6とする
nt1 = np - 1 - nt
Call n2f(nt1, n, nn)
Call f2p(n, nn, pp) '右側の文字列が配列ppに戻される
'つまりpp(1)=1，pp(2)=2，pp(3)=4，pp(4)=3です。
Next
End Sub

やっていることは
左端の番号7から，まずnt1=17を求めておきます。
次にnt1からnnを求めます。
nn(i)は17=3!*(2)+2!*(2)+1!*(1)だからnn(1)=2，nn(2)=2，nn(3)=1です。
ここでn=4のときは3!から初めて，一般には(n-1)!から始めます。
次はnnからppを求めます。ppの初期値は
pp(1)=4，pp(2)=3，pp(3)=2，pp(4)=1としておきます。
nn(1)=2ですからppの後ろから1個目から合計3個に注目して
pp(1)=4，pp(2)=2，pp(3)=1，pp(4)=3
というように配列の内容をずらします。
一般にはnn(i)のときはppの後ろからi個目から合計nn(i)+1個に注目して配列の内容をずらします。nn(1)=2，nn(2)=2，nn(3)=1ならば，順に
pp(1)=4，pp(2)=3，pp(3)=2，pp(4)=1
pp(1)=4，pp(2)=2，pp(3)=1，pp(4)=3
pp(1)=2，pp(2)=1，pp(3)=4，pp(4)=3
pp(1)=1，pp(2)=2，pp(3)=4，pp(4)=3
となります。

お礼

目的通り作っていただいたのに、理解できず済みませんでした。
動作説明まで書いていただいたので、今はまだ理解できかねますが、FORTRAＮに書き直しながら試してみます。高速化に有用かも知れないのでやってみたいと思います。
ありがとうございました。

回答No.4

f272

エクセルVBAで書いてみました。
main関数でn = 4としているところを適当に変えてください。
またmain関数でFor nt = 0 To np - 1のようにループさせていますが，これは検証のために全ケースで計算しているためです。ループさせずに1つだけでも動作します。
書き出しは
Range("A1").Offset(nt).Resize(, n - 1) = nn
Range("A1").Offset(nt, n).Resize(, n) = pp
の2つがありますが，必要なのはppの方だけでしょう。

Sub n2f(nt1 As Long, n As Long, nn() As Long)
For i = 1 To n - 1
nn(i) = 0
Next
k = 1
Do
k = k + 1
nn(n - k + 1) = nt1 Mod k
nt1 = Int(nt1 / k)
Loop While nt1 > 0
End Sub

Sub f2p(n As Long, nn() As Long, pp() As Long)
For i = 1 To n
pp(n + 1 - i) = i
Next
k = n - 1
k2 = n - 1
For i = 1 To k
j = nn(i)
t = pp(k2 + 1 - j)
For j2 = k2 + 1 - j To k2
pp(j2) = pp(j2 + 1)
Next
pp(k2 + 1) = t
k2 = k2 - 1
Next
End Sub

Sub main()
Dim k As Long
Dim n As Long
Dim np As Long, nt As Long, nt1 As Long
n = 4
ReDim nn(1 To n - 1) As Long
ReDim pp(1 To n) As Long
np = WorksheetFunction.Permut(n, n)
For nt = 0 To np - 1
nt1 = np - 1 - nt
Call n2f(nt1, n, nn)
Range("A1").Offset(nt).Resize(, n - 1) = nn
Call f2p(n, nn, pp)
Range("A1").Offset(nt, n).Resize(, n) = pp
Next
End Sub

お礼

ごへんじありがとうございます。皆様のご説明に対してのご返事の一部は、no3さんへのお礼で述べておりますので、ご参照いただければ幸いです。
vbaならば、なんとか読めそうですが、残念ながらすぐには理解できそうにありません。質問でコードをご教示を願うような文面で申し訳ありませんでしたが、やはりコードよりno1さん、NO3さんのような手順説明がわかりやすかったですね。済みませんでした。

回答No.3

m-take0220

> Ｎ個の処理を使ってn+1個の処理の形式で大分頭を悩ませましたが、ギブアップ気味です（まだ1日程度ですが）。

n=2の時は

12
21

の2通り。

n=3の時は

12のどこかに3を挿入する。場所の候補は
(a)1(b)2(c)
の(a)から(c)までの3カ所
21についても同様なので、2×3=6通り。

n=4ならn=3の時の結果から、長さ3文字に1文字挿入(4通り)、候補文字列が6つあるので4×6=24通り。

以下、同様に考えていけばいいのでは?

お礼

ご返事ありがとうございます。
そうですね、質問の最初の文字列はこの考えをもとにしました。
ただ、皆さまのご説明がそうなのですが、質問の趣旨は数列を生成することではないのです。
生成した数列に番号を割りあて後、その番号に対応した数列を求めたいのです。生成した数列は上記の考えで並べたつもりなので、なにかうまく番号から数列を計算できないかが質問でした。

その後色々考えますと、どのような方法でも、求めたいことは難しいのではと考えています。
それで、今はいずれかの方法で数列を生成し、テーブルに並べ、そのテーブルを検索する方法でコードしています。
そもそもやっていることは、ある事象がＮ個の数列パターンであらわされ、その出現頻度を計算することなので、そのパターンを1個の数値で表し、その数値の頻度を集計するようにしています。
この計算の検証のため、その数値から逆にものとの数列パターンを導きたいのが今回の質問でした。
結局前記の通り、満足するすべての数列をふくむテーブルを作り、これを検索する方法で進めています。
この方法だと計算時間がかかるため、できうれば、数列と番号の関係がテーブル検索なしに計算できればよいのですが、それは困難と思ったのですが。。。。良い方法があるでしょうか。テーブルのサイズも問題になります。

回答No.2

ballville

前、powershellで作ったのを貼っておきます。
nPn 7　で
5040個生成します。
function nPn( [int64]$N ){
filter placeN( $N ){
$ary =$_ -split ","
0..($N-1)|%{
$newarray=@()
$index=$_
0..($ary.length)|%{
if( $index -eq $_ ){
$newarray +=,$N
}
if ( $ary[$_] ){
$newarray +=$ary[$_]
}
}
$newarray -join ","
}
}

if ( $N -eq 0 ){ return $null }
if ( $N -eq 1 ){ return @(1) }
nPn ( $N - 1 )|placeN $N
}

お礼

ご返事ありがとうございます。POWERSHELLでもこんなことができるのですか。これは再帰が入っているのでしょうか残念ながら読めませんでした。

回答No.1

maiko04

a=1から7までループ
b=1から7までループ
c=1から7までループ
d=1から7までループ
e=1から7までループ
f=1から7までループ
g=1から7までループ

a=b or a=c or a=d or a=e or a=f or a=g or
b=a or b=c or b=d or b=e or b=f or b=g or
c=b or c=a or c=d or c=e or c=f or c=g or
d=b or d=c or d=a or d=e or d=f or d=g or
e=b or e=c or e=d or e=a or e=f or e=g or
f=b or f=c or f=d or f=e or f=a or f=g or
g=b or g=c or g=d or g=e or g=f or g=a

でないとき aからgまで書き出す。

こういうことかな？

お礼

ご返事ありがとうございます。
この端的な方法によると右側の文字列（ただし予定の順と異なりますが）が生成できることがわかります。その出現順に番号を振り、毎回このループを実行して、該当番号で生成した文字列が目的の文字列になることがわかりました。
ただこの方法では毎回ループを実行せねばならないところが多少残念ですが。
本来目論んだことは、該当番号から直接対応文字列を生成することなのですが、実用的には少々工夫が必要です。