Recursion problem in C
I have been trying to solve this problem for a few days, but it seems I haven't figured out the concept of recursion yet.
I need to create a C program (recursion is required here, but loops are also allowed) that does the following: The user enters 2 different lines. For example: Line 1 - ABC Line 2 - DE
The program should print lines that are concatenated with the ones entered by the user. the rule is that the internal order of letters in each line (1 & 2) must remain. This is the output for string1 = ABC and string2 = DE ":
ABCDE abdce abdec adbce adbec adebc dabce dabec daebc deabc
If someone would give me a hand here, that would be great. Thanks guys.
a source to share
Here's a partial solution in Java: it should be instructive:
public class Join { // prints:
static void join(String s, String s1, String s2) { // ABCde
if (s1.isEmpty() || s2.isEmpty()) { // ABdCe
System.out.println(s + s1 + s2); // ABdeC
} else { // AdBCe
join(s + s1.charAt(0), s1.substring(1), s2); // AdBeC
join(s + s2.charAt(0), s1, s2.substring(1)); // AdeBC
} // dABCe
} // dABeC
public static void main(String[] args) { // dAeBC
join("", "ABC", "de"); // deABC
}
}
How it works
Basically, you have an String s
"output stream" and an String s1, s2
"input stream". Whenever possible, you take c first s1
, then retry and take c s2
, recursively examining both options.
If at any time the "input stream" is empty, then you have no choice but to take whatever is left (if any).
a source to share
Here it is in C, building on the same idea by @polygenelubricants. Not that I steal his idea, it's that this is a classic problem and this is the simplest approach :).
#include <stdio.h>
#include <string.h>
void solve(const char *str1, const char *str2,
const int length1, const int length2,
char *output, int pozOut, int pozIn1, int pozIn2)
{
if (pozIn1 == length1 && pozIn2 == length2)
{
printf("%s\n", output);
return;
}
if (pozIn1 < length1)
{
output[pozOut] = str1[pozIn1];
solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1 + 1, pozIn2);
}
if (pozIn2 < length2)
{
output[pozOut] = str2[pozIn2];
solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1, pozIn2 + 1);
}
}
int main()
{
char temp[100]; // big enough to hold a solution.
solve("ABC", "12", strlen("ABC"), strlen("12"), temp, 0, 0, 0);
return 0;
}
This can be improved. For example, how would you get rid of some parameters?
It also has a bug: you have to make sure what it output
contains '\0'
at the end before printing, otherwise you might get unexpected results. I'll leave this for you to fix.
a source to share
I don't want to write down the whole algorithm. However, here are some examples that may help you.
Basically, you have to concatenate the two strings while preserving the character order. It's like you have 2 bags of different sizes.
In your example:
stack #1: A B C
stack #2: D E
You also know that the resulting string will be the length of the two input strings. (You know, you already know how much length to allocate)
If you continue character by character: each turn you can choose to put one character off stack # 1 or stack # 2 and then continue. (There might be recursion here). If you collapse all possible calls, you have all the resulting rows.
I use problems like this when I was in college: it can seem difficult at times, but it's so rewarding when you solve it yourself!
Feel free to comment if you need more hints.
a source to share
Same algorithm as IVlad, but dynamically allocates the result array and using pointers rather than indices making it clearer I think.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(const char* result, const char* x0, const char* x1, char* p) {
if (!*x0 && !*x1) printf("%s\n", result);
if (*x0) {
*p = *x0;
solve(result, x0 + 1, x1, p + 1);
}
if (*x1) {
*p = *x1;
solve(result, x0, x1 + 1, p + 1);
}
}
int main(int argc, char* argv[]) {
if (argc >= 3) {
size_t total_length = strlen(argv[1]) + strlen(argv[2]) + 1;
char *result = malloc(total_length);
if (result) {
result[total_length - 1] = '\0';
solve(result, argv[1], argv[2], result);
free(result);
}
}
return 0;
}