Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/104: Рейтинг темы: голосов - 104, средняя оценка - 4.56
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
1

Вывести всевозможные комбинации из n-чисел размером k

08.10.2014, 00:00. Показов 19916. Ответов 14
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вводим в программе n и k
n - кол-во цифр (1, 2, 3,...,n)
k - длинна выводимой комбинации
(если k=3, то должны получать 123, 124, 125..и тд)

Цифры в комб. должны идти по возростанию

Через итерацию либо рекурсию нужно проделать вывод всех возможных таких комбинаций

Понятное дело что код нужно строить через внутренние цыклы, но у меня руки дошли писать кол-во циклов равное k

C
1
2
3
4
for (int i = 1; i < 10; i++)
  for (int j = i + 1; j < 10; j++)
    for (int k = j + 1; k < 10; k++)
      printf("%d%d%d \n", i, j, k);
Нужно универсальный код для всех k и n
Буду крайне благодарен за помощь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.10.2014, 00:00
Ответы с готовыми решениями:

Сформируйте всевозможные комбинации K-значных чисел
Имеется N различных цифр a1, a2,…,an. Сформируйте всевозможные комбинации K-значных чисел,...

Из указанных чисел сгенерировать всевозможные комбинации
Как сделать такую программу. Есть пять чисел например: 1, 2, 3, 4, 5. Надо чтобы программа...

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

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

14
Guardian of Asgaard
377 / 319 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
08.10.2014, 01:57 2
Не понятно, что точно нужно сделать. Навскидку - длиной k можно обозначить размер массива, указав в нём элементы n.
0
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
08.10.2014, 02:11 3
Хм, интересно как это будет выглядеть на сишеньке. На лиспе у меня ушло 5 минут, 24 строчки (учитывая форматирование и комментарии). Алгоритм следующий (хотя у меня немного другой, но в итоге тот же):
1. формируем сочетания из n по k.
2. из каждого сочетания формируем число
3. отфильтровываем числа, меньшие чем 10^(k - 1) (это возможно если в множестве n есть 0)
4. сортируем по возростанию.
Например, есть множество n = {1,2,3} и k = 2, сочетания:
{1,2} -> 12
{1,3} -> 13
...
{3,2} -> 32.

Добавлено через 1 минуту
ну и множество n соответственно должно быть не более 10 (0..9).
0
585 / 488 / 371
Регистрация: 05.11.2013
Сообщений: 1,265
Записей в блоге: 6
08.10.2014, 06:24 4
Лучший ответ Сообщение было отмечено Emisare как решение

Решение

вот сочетания или "цэшки"
не понял - 12 и 21 - у тебя должны быть разные сочетания или одно и то же?
можно так и так делать
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
const int n1=20;
int k,n,a[n1],p[n1];
 
void cnk(int m,int l) {
 //m-сколько осталоась выбрать,l - номер элемента с которого начниаем
 int i,j;
 if (m==0) { //Здесь - обработка комбинации
  printf ("\n");
  for (j=0;j<k;j++) printf ("%d ",p[j]);
 }
 else for (i=l;i<=n-m;i++) {
   p[k-m]=a[i];
   cnk(m-1,i+1);
 }
}
 
int main ()  {
 printf ("\nПодмножества из N по K");
 printf ("\nВведите N (2-%d):",n1);
 fflush (stdin);
 scanf("%d",&n);
 printf ("\nВведите K:");
 fflush (stdin);
 scanf("%d",&k);
 for (int i=0;i<n;i++) a[i]=i+1; //данный массив может быть заполнен произвольно
 cnk(k,0);
 fflush (stdin); getchar();
}
Введите N (2-20):3

Введите K:2

1 2
1 3
2 3
1
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
27.10.2014, 16:08  [ТС] 5
все же, хочу понять как можно реализовать данную задачу без рекурсии
именно чистой итерацией
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
27.10.2014, 21:45 6
Без рекурсии

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
 
unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}
 
#define N 9u
#define K 3u
 
int main()
{
  const char *digits = "123456789";
  unsigned subset;
 
  for (subset = (1 << K) - 1; subset < (1 << N); subset = next_combination(subset))
  {
    unsigned bit, i;
 
    for (bit = 1, i = 0; bit < (1 << N); bit <<= 1, ++i)
      if ((subset & bit) != 0)
        printf("%c", digits[i]);
 
    printf("\n");
  }
 
  return 0;
}
Реализация функции 'next_combination' взята отсюда: http://en.wikipedia.org/wiki/C... ber_system

При этом пользоваться вот этими битовыми трюками не обязательно. Там же по ссылке описан алгоритм, как от одного подмножества размера K перейти к следующему подмножеству.

Добавлено через 2 минуты
Цитата Сообщение от Emisare Посмотреть сообщение
Нужно универсальный код для всех k и n
Ну во-первых, понятно, что k <= n. Иначе задача не имеет решения.

А во-вторых, что вы предлагаете использовать в качестве цифр для n=20? Для n=100? Для n=1024?
1
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
27.10.2014, 22:07  [ТС] 7
ну, по условию, для n=100 и тд, мы используем все числа от 2 до 100, но так же можно ограничить n в дефайне, что бы не переусердствовать.

думаю, что битовые операции мне стоит переделать
за ссылку - спасибо

Добавлено через 9 минут
и все же меня попросили сделать задачу без дополнительных вызовов функции в мейне
0
Boleon
27.10.2014, 23:56
  #8

Не по теме:

Цитата Сообщение от Emisare Посмотреть сообщение
и все же меня попросили сделать задачу без дополнительных вызовов функции в мейне
а позже окажется, что делать нужно было на Паскале

0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
28.10.2014, 02:49 9
Цитата Сообщение от Emisare Посмотреть сообщение
и все же меня попросили сделать задачу без дополнительных вызовов функции в мейне
Никто вам не мешает скопировать текст функции прямо в 'main' и тем самым избавиться от вызова.
0
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
05.11.2014, 23:15  [ТС] 10
Кстати, ваш способ ефективен только для n<10

Для реализации задачи полностью, мне посоветовали взять 2 цикла while
Сначало заполним первую последовательность как
5 6 7 8 9 при n=9, k=5
а дальше будем уменьшать по очереди елементы
например дальше будет
4 6 7 8 9
3 6 7 8 9
и так до 1 2 3 4 5

Реализовать пока не получается, но способ довольно простой
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
05.11.2014, 23:30 11
Цитата Сообщение от Emisare Посмотреть сообщение
Кстати, ваш способ ефективен только для n<10
Мой способ эффективен для любого значения N.

Моя реализация работает только для N, которое не превышает разрядности максимального целочисленного типа на платформе. Все что надо сделать, это договориться, что мы будем использовать для представления "цифр" при N > 10 и подправить код соотв. образом. Если N превышает разрядность максимального целочисленного типа на платформе, то придется обойтись без битовых операций, а реализовывать алгоритм перечисления подмножеств, как описано по ссылке в Википедии.

В обоих случаях мы получаем очень эффективные алгоритмы.

Добавлено через 2 минуты
Цитата Сообщение от Emisare Посмотреть сообщение
но способ довольно простой
Ну раз простой, то и реализовать его должно быть несложно, так?

Но выглядит перспективно. В принципе, почему бы не идти по возрастанию от 12345, 12346, ..., 12349, 12356, 12357, ..., 56789?
0
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
05.11.2014, 23:34  [ТС] 12
Для меня ваш подход совсем незнаком
В моей ситуации можно пожертвовать эффективностью
Главное - работоспособность и адекватный вывод при любом значение n
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
05.11.2014, 23:56 13
Цитата Сообщение от Emisare Посмотреть сообщение
В моей ситуации можно пожертвовать эффективностью
Тут нет никакого жертвования. Ваш алгоритм действительно эффективнее моего. Вот моя реализация вашего алгоритма в восходящей версии

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
 
#define N 10u
#define K 3u
 
int main(void) {
  unsigned digits[K];
  unsigned i;
 
  for (i = 0; i < K; ++i)
    digits[i] = i + 1;
 
  do {
    unsigned overflow;
 
    for (i = 0; i < K; ++i)
      printf("[%u]", digits[i]);
    printf("\n");
 
    for (i = K - 1, overflow = N; i != -1; --i, --overflow)
      if (++digits[i] < overflow)
        break;
 
    if (i == -1)
      break;
 
    for (++i; i < K; ++i)
      digits[i] = digits[i - 1] + 1;
 
  } while (1);
}
Однако тут сразу очевидна одна тонкость, которая содержится в условии задачи. Так как мы работаем с обобщенным "цифрами", то возникает вопрос, есть ли у нас цифра "нуль", т.е. цифра, которая "становится невидимой" и "не считается", если ее поместить в начало числа? Реализация выше, считает, что есть. Соответственно требуется, чтобы K было меньше, чем N. Иначе задача не имеет решения. Я не проверяю это условие в коде.
1
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
06.11.2014, 00:00  [ТС] 14
вариант с циклом for тут более уместен чем while кстати
благодарю за реализацию
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
13.11.2014, 22:59 15
del
0
13.11.2014, 22:59
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.11.2014, 22:59
Помогаю со студенческими работами здесь

Найти всевозможные комбинации чисел, которые можно получить из одного числа
Здравствуйте , собственно суть задачи: Надо написать программу которая находит все возможные...

Всевозможные комбинации
Даны три цифры,из них составить всевозможные трехзначные числа. Н-р: 5,8,3 Получить: 583 538...

Составить всевозможные комбинации трех букв
подскажите кто знает как можно сделать подобное: есть 3 буквы к примеру А,Б,В , необходимо создать...

Как посчитать всевозможные комбинации строки
Допустим есть слово &quot;Пример задачи&quot;. Стоит цель заменить русские буквы на аналогичные английские. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru