推 lightspeed:推b! 10/18 18:00
推 hardcover:帥啊 XD 10/18 20:46
推 icestar3:好利害…真的!! 受小弟一拜 0rz 10/18 21:37
※ 引述《icestar3 (☆植村秀化妝水☆)》之銘言：
: 我的問題是這樣的
: 假設我現在有十個球分別編號為1,2,3,4,5,6,7,8,9,10
: 我的input data每次都會跟我說我要用到哪幾個球
: 舉例來說，如果我這次用到的是1,3,5,7,9
: 則我的input data的型式會是
: 1 2 3 4 5 6 7 8 9 10
: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
: 接著假設我現在要做的是"每次取三個球"(輸入參數P會指定要每次取幾個)
: 所以我第一次要做的是C5取3的排列情形；
: 接著要做第二次，因為C5取3取完了之後，還剩下兩個球沒取到(5顆球都要取完)
: 但是我每次都要固定做取3的動作，現在只剩下兩個球，所以，第二次的組合情形
: 就要從前一輪取過的三個球裡面"任意"拿一個到第二輪裡湊成3個，要呈現出全部
: 的排列情形
: 再舉一個例子好了
: 如果我這次要用到四個球ex:[1,3,5,7]，還是一樣每次取三3個， 那
: 我第一次做就是C4取3，但是因為每次都固定要要取3個，第二次只剩
: 下1顆球沒被取，所以要從前一輪裡做c3取2，拿兩個球放到第二輪
: 這樣的全部的排列情形就會有
: 135 713; 135 715; 135 735;
: 137 513; 137 517; 137 537;
: 157 315; 157 317; 157 357;
: 357 135; 357 137; 357 157;
: 12種情形 (C4取3*C3取2=12)
: 再舉一個例子，大家應該能更了解我的意思
: 如果我這次用到6個球，然後要做每次2個的選取(P=2)，那麼我第一次就做C6取2
: 的選取，第二次就是做C4取2的選取(第一次選完後剩下來的四個中任意選兩個)
: 第三次就是做C2取2的選取，然後要列出全部的排列情形。
: 因為使用的球是6個，每次則要選2個，最後會剛剛好被選完，所以就沒有上面兩個
: 例子裡，還要從前一輪選取的球中填滿最後一輪球會不足選取的問題
: (使用的球的個數能被每次要取的球數給整除的話)
這是一題很奇怪的排列組合 所以很好奇它的出處
你的程式我看不懂 不過自己寫一次倒是比較快 程式利用到兩次遞迴
與 C++ 的 STL 可以用來練練 STL 功力
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <cmath>
using namespace std ;
// print container
template <typename Iter>
void print_container( Iter start , Iter end , int n ) {
int j ;
for ( Iter iter = start ; iter != end ; iter += n ) {
cout << "( " ;
for ( j = 0 ; j < n ; ++j ) cout << *(iter+j) << " " ;
cout << ") " ;
}
cout << endl ;
}
// output all possible n elements from a sequence [start,end)
template <typename Iter , typename T >
void select( Iter start , Iter end , int n , vector<T>& bar ,
vector< vector<T> >& result ) {
if ( bar.size() == n ) {
result.push_back( bar ) ;
} else {
for ( Iter iter = start ; iter != end ; ++iter ) {
bar.push_back(*iter) ;
select( iter+1 , end , n , bar , result ) ;
bar.pop_back() ;
}
}
}
template <typename Iter, typename T>
void special_select( Iter start , Iter end , int n , vector<T>& b ) {
vector< vector<T> > r ;
vector<T> bar , no ;
int i , j ;
static int count = 0 ;
if ( end < start + n ) {
select( b.begin() , b.end() , n + start - end , bar , r ) ;
copy( start , end , back_inserter(b) ) ;
for ( i = 0 ; i < r.size() ; ++i ) {
cout << setw(3) << ++count << " : " ;
copy(r[i].begin(),r[i].end(),back_inserter(b)) ;
print_container( b.begin() , b.end() ,n ) ;
for ( j = 0 ; j < r[i].size() ; ++j ) b.pop_back() ;
}
for ( j = 0 ; j < end-start ; ++j ) b.pop_back() ;
} else if ( end == n + start ) {
copy( start , end , back_inserter(b) ) ;
cout << setw(3) << ++count << " : " ;
print_container( b.begin() , b.end() , n ) ;
for ( j = 0 ; j < n ; ++j ) b.pop_back() ;
} else {
select( start , end , n , bar , r ) ;
for ( i = 0 ; i < r.size() ; ++i ) {
copy(r[i].begin(),r[i].end(),back_inserter(b)) ;
set_difference(start,end,r[i].begin(),r[i].end(),back_inserter(no)) ;
special_select(no.begin(),no.end(),n,b) ;
for ( j = 0 ; j < n ; ++j ) b.pop_back() ;
no.resize(0) ;
}
}
}
int main() {
const int S = 6 ;
int no[S] = { 1 , 3 , 5 , 7 , 9 };
int m = 4 , n = 3 ;
vector<int> bar ;
special_select( no , no+m , n , bar ) ;
return 0 ;
}
輸出 :
1 : ( 1 3 5 ) ( 7 1 3 )
2 : ( 1 3 5 ) ( 7 1 5 )
3 : ( 1 3 5 ) ( 7 3 5 )
4 : ( 1 3 7 ) ( 5 1 3 )
5 : ( 1 3 7 ) ( 5 1 7 )
6 : ( 1 3 7 ) ( 5 3 7 )
7 : ( 1 5 7 ) ( 3 1 5 )
8 : ( 1 5 7 ) ( 3 1 7 )
9 : ( 1 5 7 ) ( 3 5 7 )
10 : ( 3 5 7 ) ( 1 3 5 )
11 : ( 3 5 7 ) ( 1 3 7 )
12 : ( 3 5 7 ) ( 1 5 7 )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.25.22