Arkadaşlar kombinasyon algoritmasını bulmaya çalışıyorum ama henüz esnek olarak çıkaramadım. örnek vermek gerekirse 1'den 5'e kadar olan sayılar kaç farklı şekilde dizilebilir? Bunu hesaplayabiliyoruz 5!. Benim bu dizilimlere ihtiyacım var. Ama esnek olacak.
Bilen varsa paylaşırsa sevinirim.
kombinasyon algoritması
Forum kuralları
Forum kurallarını okuyup, uyunuz!
Forum kurallarını okuyup, uyunuz!
Kod: Tümünü seç
#include <algorithm>
namespace benbear
{
using namespace std;
// BiIterator :: Binary Direction Iterator
/**** sort_combination *********
*
* merge sort needed by benbear::combination
*/
template <typename BiIterator>
void
sort_combination (BiIterator first, BiIterator last)
{
if (first == last) // no element
return;
BiIterator i = first;
++i;
if (i == last) // one element
return;
int half = distance (first, last) / 2; // half of the length
BiIterator middle = first;
advance (middle, half); // middle += half
sort_combination (first, middle); // sort first part
sort_combination (middle, last); // sort second part
inplace_merge (first, middle, last); // merge two parts
}
/******* adjust_combination ********
*
* adjust the ranges, [first, middle) and [middle, last), to a
* standard combination sequence
*/
template <typename BiIterator>
void
adjust_combination (BiIterator first, BiIterator middle, BiIterator last)
{
// the front part or the back part have no elements
if (first == middle)
{
sort_combination (middle, last);
return;
}
if (middle == last)
{
sort_combination (first, middle);
return;
}
sort_combination (first, middle);
sort_combination (middle, last);
BiIterator b = middle;
--b;
BiIterator j = lower_bound (middle, last, *b);
// [j, last) is the range which is not small than the last element
// of the front part
reverse (j, last);
reverse (middle, last);
}
/*********** init_combination *********
*
* initialize the ranges to the first or last of the standard
* combination sequences
*/
template <typename BiIterator>
void
init_combination (BiIterator first, BiIterator middle, BiIterator last,
bool min)
{
// this is the min combination sequence
sort_combination (first, last);
if (min == false) // max ?
{
// the max combination
reverse (first, last);
reverse (first, middle);
}
}
/************ next_combination ***************
*
* get the next (bigger) combination sequence of current sequence
*/
template <typename BiIterator>
bool
next_combination (BiIterator first, BiIterator middle, BiIterator last)
{
// the front or the back part is empty, only need to sort them
if ((first == middle) || (middle == last))
return false;
BiIterator b = middle; // last element of [first, middle)
--b;
if (*b < *middle)
{
// *b < *middle, then *b is just the element which we look for
BiIterator j = b;
while ((++b != last) && (*j < *b))
{
iter_swap (j, b);
j = b;
}
return true;
}
BiIterator e = last; // biggest of the back part
--e;
while (e != middle)
{
BiIterator k = e;
--k;
if (!(*k < *e))
e = k;
else
break;
} // get the biggest `e'
BiIterator f = e; // right element of the *e
++f;
while ((f != last) && !(*f < *e))
++f;
if (!(*first < *e))
{
// the front part is bigger than the back part,
// it's the max combination sequence
reverse (first, middle);
reverse (first, last);
return false;
}
if (*b < *e)
{
// target element will be found in [middle, e]
BiIterator bb = b;
while ((++bb != e) && !(*b < *bb))
;
reverse (bb, f);
reverse (b, f);
}
else
{
BiIterator i = b; // `i' is the max element select out
while (!(*--i < *e))
;
BiIterator j = last; // `j' is the min element select in
while (!(*i < *--j))
;
// now, *j > *i. replace *i with *j, then adjust the
// combination sequence
iter_swap (i, j);
reverse (++i, middle);
reverse (i, j);
}
return true;
}
/**************** prev_combination **************
*
* get the previous (smaller) combination sequence of the current
* sequence
*/
template <typename BiIterator>
bool
prev_combination (BiIterator first, BiIterator middle, BiIterator last)
{
// the front or the back part is empty, only need to sort them
if ((first == middle) || (middle == last))
return false;
BiIterator b = middle;
--b;
if (*middle < *b)
{
BiIterator i = upper_bound (first, middle, *middle);
if (i != b)
iter_swap (i, middle);
else
{
BiIterator s = middle;
while ((++s != last) && !(*s < *middle))
;
reverse (b, s);
}
return true;
}
BiIterator e = last;
--e;
while (e != middle)
{
BiIterator k = e;
--k;
if (!(*k < *e))
e = k;
else
break;
}
BiIterator f = e;
++f;
while ((f != last) && !(*f < *e))
++f;
if (f == last)
{
reverse (first, last);
reverse (first, middle);
return false;
}
BiIterator i = upper_bound (first, middle, *f);
if (i == b)
{
BiIterator s = f;
while ((++s != last) && !(*s < *f))
;
reverse (b, f);
reverse (b, s);
}
else
{
iter_swap (i, f);
reverse (++i, f);
reverse (i, middle);
}
return true;
}
} // end of namespace benbear
// for test:
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
template <typename BiIterator>
void
show_array (BiIterator f, BiIterator m, BiIterator l)
{
while (f != m)
cout << *f++;
cout << " ";
while (f != l)
cout << *f++;
cout << endl;
}
template <typename BiIterator>
void
combi (BiIterator f, BiIterator m, BiIterator l, bool next)
{
benbear::init_combination (f, m, l, next);
int c = 0;
cout << endl;
do
{
show_array (f, m, l);
c++;
}
while (next ? benbear::next_combination (f, m, l)
: benbear::prev_combination (f, m, l));
cout << "The end: ";
show_array (f, m, l);
cout << "There's: " << c << endl;
}
int
main ()
{
int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
bool dir = false;
for (int i = 1; i < 10; i++)
{
random_shuffle (a, a+7);
sort (a, a+3);
benbear::adjust_combination (a, a+3, a+7);
show_array (a, a+3, a+7);
}
for (int i = 1, j = 9; i < j; i++)
{
combi (a, a+i, a+j, dir);
}
sort (a, a+9);
benbear::sort_combination (a, a+7);
a[1] = 1;
a[4] = 6;
//a[6] = 6;
for (int i = 1, j = 7; i < j; i++)
{
combi (a, a+i, a+j, dir);
}
int n;
cout << "The n: ";
cin >> n;
vector<int> vec(n);
cout << "please. input numbers: " << endl;
for (int i = 0; i < n; i++)
cin >> vec[i];
for (int i = 1; i < n; i++)
{
combi (vec.begin(), vec.begin()+i, vec.end(), dir);
}
return 0;
}delphi koduna dönüştürebilirsin umarım.
Kod: Tümünü seç
Program Combination;
var
index_arr : array[1..5] of byte;
combi_arr : array[1..10] of byte;
index,increament,n,r : byte;
c : byte;
procedure show_arr;
var
i : byte;
begin
inc(c);
for i:=1 to r do
write(combi_arr[index_arr[i]]);
writeln;
end;
procedure set_arrangement(index : byte);
var
i : byte;
begin
inc(index_arr[index]);
for i:=index+1 to r do
index_arr[i]:=index_arr[i-1]+1;
end;
procedure combi(index,increament : byte);
var
i : byte;
begin
if (increament<=n) then
begin
index_arr[r]:=increament;
show_arr;
combi(index,increament+1);
for i:=r-1 downto index do
if (index_arr[index]<n-(r-index)) then
begin
set_arrangement(i);
combi(i,index_arr[r]);
end;
if (index>1) and (index_arr[1]<=(n-r)) then
begin
set_arrangement(index-1);
combi(index-1,index_arr[r]);
end;
end;
end;
var
i : byte;
begin
write('Enter n:');
readln(n);
write('Enter r:');
readln(r);
c:=0;
writeln;
for i:=1 to n do
combi_arr[i]:=i;
for i:=1 to r do
index_arr[i]:=i;
combi(r,index_arr[r]);
writeln('The total counting is ',c);
end.
1'den 5'e kadar olan sayıların farklı dizilimlerine permütasyon denir. Kombinasyon farklı bir şey.
Ayrıca yukarıdaki C++ kodunda hem algorithm headerini ekleyip hem de o kadar uzun bir kod nasıl yazmışlar anlamak mümkün değil
Ayrıca yukarıdaki C++ kodunda hem algorithm headerini ekleyip hem de o kadar uzun bir kod nasıl yazmışlar anlamak mümkün değil
Kod: Tümünü seç
#include <iostream>
#include <algorithm>
#include <vector>
#define fori(i,c) for(int i = 0;i<(c);i++)
using namespace std;
int main(int argc, char *argv[])
{
vector<int> list;
fori(i,5) list.push_back(i+1);
do {
fori(i,5) cout << list[i];
cout << endl;
} while(next_permutation(list.begin(),list.end()));
system("PAUSE");
}