Member Avatar for Linking_90

Hi,

I was hoping that someone could give me some direction with how to solve this probem.

The only info in this problem is
word has N digits[only digits] and the numbers (output) should be in increasing order example 1469 or 468

The output should give all combinations in the increasing order

Example :
Enter length of number : 3

This output should give all numbers without recursion in increasing order for numbers between [0-9].

Thanks,
Cathy

  • 4 Contributors
  • 6 Replies
  • 127 Views
  • 23 Hours Discussion Span
  • Latest Post Latest Post by Linking_90

Dani AI

Generated

This problem is to generate all strictly increasing digit sequences of length N from the digits 0..9 (examples: 1469 or 468), printed in lexicographic/increasing order and without recursion. N must be between 1 and 10 (there are C(10,N) outputs; for N=3 there are 120). is correct that recursion is a natural approach; pointed in the right direction with “increment right-to-left”; showed a brute-force test-by-number method that works but checks many irrelevant values. Below is a compact, iterative (non-recursive) implementation that implements the standard lexicographic “next combination” step: find the rightmost digit that can be incremented, increment it, then set all digits to its right to the immediate successive values.

#include <iostream>
#include <vector>

void print_combinations(int k, bool allowLeadingZero = true) {
    if (k <= 0 || k > 10) { std::cout << "Length must be 1..10\n"; return; }
    if (!allowLeadingZero && k > 9) { std::cout << "No combos without leading zero for length > 9\n"; return; }

    std::vector<int> a(k);
    int start = allowLeadingZero ? 0 : 1;
    for (int i = 0; i < k; ++i) a[i] = start + i;

    while (true) {
        for (int d : a) std::cout << d;
        std::cout << '\n';

        int i = k - 1;
        while (i >= 0 && a[i] == 9 - (k - 1 - i)) --i;
        if (i < 0) break;

        ++a[i];
        for (int j = i + 1; j < k; ++j) a[j] = a[j - 1] + 1;
    }
}

Notes and troubleshooting:

  • If leading zeros are not wanted, call with allowLeadingZero = false; then k cannot exceed 9.
  • Common bugs to watch for (seen in earlier posts): using == where you meant =, off-by-one limits (the max value for position i is 9 - (k-1-i)), mismatched types (storing numeric digits in a char but printing as a number), and relying on nonstandard VLAs in C++ — prefer std::vector/std::string.
  • Complexity is O(C(10,k) * k) time and O(k) memory, which is optimal for enumerating combinations.

Recommended Answers

All 6 Replies

Member Avatar for Denniz

I believe you need to use recursive functions.

Member Avatar for Salem

Start at the right, increment it by 1, then scan to the left to see what else can be incremented.

Member Avatar for Linking_90 
//This code will I guess increment the last digit example
012
013
014
.
.
019

The next number I guess would be to 023,024....
Can someone guide me as to how or where can I  make this change in the code.
 
void PrintNumbers (int length)
{
  int a[] ={0,1,2,3,4,5,6,7,8,9};
  char result [length + 1];
  int i;

  for (i=0;i<length;i++)
  result[i]= a[i];
  
 //Main loop begins here
  while (1) {
   printf (  "%d"\n",result);
   
  for (i=length-1 ; i>=-1;i--)
  {
    if (i==-1) return;
   
    if (a[i] == result [i]) {
    resullt [i] == a[i+1];
    break;
   }
 }
}    
}
Member Avatar for dougy83

Obviously recursion would enable a simpler/cleaner approach, if it were allowed.

There is no mention of need for speed/efficiency in the problem statement, so it may be perfectly valid to just use a dirty brute-force method:

#include <iostream>
#include <iomanip>
#include <sstream>
using namespace std;

bool numberValid(int v, int len){
   int oldd = 10;
   for(int i = 0; i < len; i++){
      int d = v % 10;
      v /= 10;

      if(d >= oldd)
         return false;     // non-increasing progression
      
      oldd = d;
      }
   
   return true;      // valid
   }
   
main(){
   int len;
   cout << "Enter len: ";
   cin >> len;
   cin.get();
   
   int maxVal = (int[]){9, 89, 789, 6789, 56789, 456789, 3456789, 23456789, 123456789, 123456789}[len-1];

   for(int i = 0; i <= maxVal; i++){
      if(numberValid(i, len)){
         cout << setw(len) << setfill('0') << i << endl;
         }
      }
   
   cin.get();
   }
Member Avatar for dougy83

Start at the right, increment it by 1, then scan to the left to see what else can be incremented.

You would only scan to the left if a more-right digit couldn't be incremented - in which case you would try to increment a digit to the left. When you find a digit that can be incremented, you would increment it then set all digits to the right of it equal to 1 more than the digit to their left.

Apparently English is my first language, but good luck understanding what I've just written; I'm sure it made sense when I wrote it.

Member Avatar for Linking_90

dougy83 thank you very much. That was a perfect !!!!
-Cathy

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.