Сочетания и алгоритм их получения

[Ksardas13]

Устал гуглить, а заказик сдавать через несколько часов. Всё то работает, но одна процедура сделана по шумок, типа пока пусть будет так... вот хочу всё сделать на совесть.

Есть массив от "0" до "n-1" с элементами равными (1,2,3,...,n). Нужно создать функцию: закидываем этот массив, количество его элементов и на выходе получаем наш же массив, но первые m элементов(где m<n) составляют новое сочетание(т.е. функция переставляет местами элементы массива).
И вот наша задача вставить такую функцию в цикл от "1" до "возможного количества сочетаний для данного массива", приписать в этом же цикле под нашей функцией вывод на экран массива(первых m членов достаточно). В итоге получить следующее:

Для 4 позиций(m=4) и шести элементов(n=6) массив выглядит так: 1,2,3,4,5,6. Должны получить:

1234
1235
1236
1245
1246
1256
1345
1346
1356
1456
2345
2346
2356
2456
3456

Помогите с алгоритмом. Заранее благодарен.

[Vago]

Что-то сегодня народ здесь на комбинаторику потянуло!..
...

Сообщение от Ksardas13

...наша задача вставить такую функцию в цикл от "1" до "возможного количества сочетаний для данного массива", приписать в этом же цикле под нашей функцией вывод на экран массива(первых m членов достаточно)...

Как по мне - лучше вставлять не в цикл, а в саму себя.

Сообщение от Ksardas13

Помогите с алгоритмом. Заранее благодарен.

#!/usr/bin/python
# -*- coding: cp1251 -*-

a = ['1', '2', '3', '4']
m = 2
z = range( m )


def Cnm( a, j ):
    if j <= m:
        for i in range(0,len(a) ):
            z[j-1] = a[i]
            _a = []
            for l in range(i+1,len(a) ):
                _a.append( a[l] )
            Cnm( _a, j+1 )
    else:
        print z
        return

Cnm( a, 1 )

#

На Цэ сами переложите, надеюсь?..

[Rififi]

Ksardas13

Помогите с алгоритмом. Заранее благодарен.

алгоритм называется lulz
здесь демонстрация его применения

[Spawn™Production®]

А смысл при данных условиях делать перестановку элементов массива? Решается-то всё несколькими циклами...

[Ksardas13]

Спасибо большое, буду копаться.))

А смысл при данных условиях делать перестановку элементов массива? Решается-то всё несколькими циклами...

Эм, наверное я плохо понял ваше предложение, но... Пусть N=100, а M=50. Во сколько тогда превратится "несколько циклов"?))
Пример с n=6 это всего лишь пример.)

Как по мне - лучше вставлять не в цикл, а в саму себя.

Желание заказчика порой бывают извращённы.))
Пытаюсь удовлетворить.)

[Spawn™Production®]

Во сколько тогда превратится "несколько циклов"?))

Столько же, сколько и при N=100000;

[Ksardas13]

Ага, начинаю понимать что Вы имеет ввиду! Наверное. Вот вчера ночью пытался эти циклы вывести... Не подскажете какой они имеют вид?
Первое на чём остановился - это цикл тупо сдвигающий массив влево(а первый элемент идёт на место последнего) до тех пор, пока он не вернётся в исходное состояние. Так получаем 6 комбинаций из 15-ти приведённых в примере. Как получить остальные?

[Vago]

Сообщение от Ksardas13

Желание заказчика порой бывают извращённы.))
Пытаюсь удовлетворить.)

В смысле? Заказчик поставил жёсткое условие - не использовать рекурсию?

[Ksardas13]

Заказчик студент. Задание из некой криво написанной методы для преподши, которая С++ читает впервые(я сам в шоке)).
Вот там строго прописана процедура, возвращающая перестановки массива(номеров массива), которая крутится в почти бесконечном цикле, пока не выполнится определённое условие(ищем геометрические фигуры, среди множества точек).
Но приведённая процедура в методе не даёт всех сочетаний... вот мучаюсь как бы её исправить -_-

Если б не это ограничение, мозг бы болел меньше.

[Vago]

Сообщение от Ksardas13

... которая С++ читает впервые(я сам в шоке)).

Всё в этой жизни когда-нибудь приходится делать впервые...
...
Ну, держите ещё с индексами, без выдёргивания подмассива.

#include <iostream>
using namespace std ;

int* a ;
const int  n = 5 ,
           m = 3 ;


void PrintCnm( int* a ) {

   for ( int i = 0; i < m; i++ )
      cout << a[i] << ' ' ;
   cout << endl ;

}


void Cnm( int k ) {

   if ( k >= 0 ) {
// BAD! BAD!! BAD!!!      if ( a[k] < n+k-1 ) {
      if ( a[k] < n+k-m+1 ) {
         ++a[k] ;
         for ( int i = k+1; i < m; i++ ) 
            a[i] = a[i-1]+1 ;
         PrintCnm( a ) ;
         Cnm( m-1 ) ;
      } else
         Cnm( k-1 ) ;
   } else
      return ;

}


int main() {

   a = new int[m] ;

   for ( int i = 0; i < m; i++ )
      a[i] = i+1 ;
   PrintCnm( a ) ;

   Cnm( m-1 ) ;

   delete []a ;      

   return 0 ;

}

Added 19:47 CET:
Извините, с верхним пределом цикла в одном месте ошибся.