سازندهی میکستیپ

واژگان math.combinatorics به دو نوع پرسش درباره‌ی مجموعه‌ای از عنصرها پاسخ می‌دهد:

• ترکیب‌ها: به چند روش، یا به کدام روش‌ها، می‌توانید گروهی را انتخاب کنید، بدون توجه به ترتیب؟
• جایگشت‌ها: به چند روش، یا به کدام روش‌ها، می‌توانید عنصرها را مرتب کنید، جایی که ترتیب اهمیت دارد؟

برای هر پرسش، یک واژه‌ی شمارش هست که عددی برمی‌گرداند و یک واژه‌ی فهرست‌سازی که خود انتخاب‌ها را برمی‌گرداند.

شمارش

nCk («n انتخاب از k») برمی‌گرداند که از میان n عنصر، چند ترکیب kعضوی می‌توان انتخاب کرد:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

5 2 nCk .    ! => 10
6 3 nCk .    ! => 20
5 5 nCk .    ! => 1

nPk برمی‌گرداند که از میان n عنصر، چند انتخاب مرتب kعضوی (یعنی جایگشت) می‌توان ساخت. چون ترتیب مهم است، این شمارش دست‌کم به بزرگی nCk متناظر است:

nPk ( n k -- m )

5 2 nPk .    ! => 20
6 3 nPk .    ! => 120

فهرست‌سازی ترکیب‌ها

all-combinations هر زیرمجموعه‌ی kعضوی از یک دنباله را برمی‌گرداند. عنصرهای درون هر ترکیب ترتیب اصلی خود را حفظ می‌کنند و ترکیب‌ها به ترتیب واژه‌نامه‌ای برگردانده می‌شوند:

all-combinations ( seq k -- combinations )

{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }

وقتی می‌خواهید هر ترکیب را همان‌طور که تولید می‌شود پردازش کنید و نه همه‌شان را جمع کنید، از شکل جریانی each-combination استفاده کنید که برای هر ترکیب یک «بلوک کد» را فراخوانی می‌کند:

each-combination ( seq k quot -- )

{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }

فهرست‌سازی جایگشت‌ها

all-permutations هر ترتیب ممکن از یک دنباله را برمی‌گرداند:

all-permutations ( seq -- permutations )

{ 1 2 } all-permutations .
! => { { 1 2 } { 2 1 } }

{ 1 2 3 } all-permutations .
! => { { 1 2 3 } { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 1 2 } { 3 2 1 } }

همتای جریانی آن each-permutation است که برای هر ترتیب یک بلوک کد را فراخوانی می‌کند:

each-permutation ( seq quot -- )

{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }