• Status: Solved
• Priority: Medium
• Security: Public
• Views: 640

# string combinatorics, generate nCr strings from n strings

I have a set of n strings. I would like to extract all combinations of strings from these n strings . (all nCr combinations). How can  I do this programmatically.
For example :
Input : a,b,c,d,e
Output :
a,b,c,d
a,b,c,e
a,b,d,e
a,c,d,e
b,c,d,e
a,b,c
a,c,d
a,d,e
......and so on till

a,b
b,a
and so on till
a
b
c
d
e
0
TrialUser
• 5
• 2
1 Solution

Commented:
The best way is to make a function that finds all string combinations of length N and use that recursively.
Then you just call it for each length.

``````
ArrayList FindAllStrings(string input)
{
ArrayList strings;

for(int i = 0; i<=input.Length(); i++)
}

{
if(N == 0)
else
{
for(int i = 0; i + N < input.Length(); i++)
}
``````
0

Commented:
Tested and fixed
``````        private ArrayList FindAllStrings(string input)
{
ArrayList strings = new ArrayList();

for (int i = 0; i <= input.Length; i++)

return strings;
}

private void AddStrings(ArrayList strings, string input, int N, string leading = "")
{
if (N == 0)
else
{
for (int i = 0; i + N <= input.Length; i++)
}
}
``````
0

Commented:
If you want the commas, change line 18 to
AddStrings(strings, input.Substring(i + 1), N - 1, leading + (leading.Length > 0 ? ",":"") + input[ i]);
0

Middle School Assistant TeacherCommented:
Use the libaray here written by Adrian Akison:
http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Simple Demo: Idle-Mind-502573.flv

Click on Project --> Add Reference --> Browse --> Facet.Combinatorics.dll

Then you want to use the Variations class like this:
``````using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{
listBox1.DataSource = Variations(textBox1.Text);
}

private List<string> Variations(string input)
{
List<string> values = new List<string>();
for (int i=0; i < input.Length; i++)
{
}

List<string> results = new List<string>();
for (int i = input.Length; i >= 1; i--)
{
Facet.Combinatorics.Variations<string> vars = new Facet.Combinatorics.Variations<string>(values.AsReadOnly(), i);
foreach (IList<string> set in vars)
{
}
}
return results;
}
}
}
``````

Here's the output:
``````a,b,c,d
a,b,d,c
a,c,b,d
a,d,b,c
a,c,d,b
a,d,c,b
b,a,c,d
b,a,d,c
c,a,b,d
d,a,b,c
c,a,d,b
d,a,c,b
b,c,a,d
b,d,a,c
c,b,a,d
d,b,a,c
c,d,a,b
d,c,a,b
b,c,d,a
b,d,c,a
c,b,d,a
d,b,c,a
c,d,b,a
d,c,b,a
a,b,c
a,b,d
a,c,b
a,d,b
a,c,d
a,d,c
b,a,c
b,a,d
c,a,b
d,a,b
c,a,d
d,a,c
b,c,a
b,d,a
c,b,a
d,b,a
c,d,a
d,c,a
b,c,d
b,d,c
c,b,d
d,b,c
c,d,b
d,c,b
a,b
a,c
a,d
b,a
c,a
d,a
b,c
b,d
c,b
d,b
c,d
d,c
a
b
c
d
``````

0

Commented:
Idle_Mind, that does all the possible permutations of all the possible combinations. It's also using another library and even then, the code looks just about as long as mine.

TrialUser, I assume your inclusion of both a,b and b,a was accidental and you just wanted the combinations. To do all permutations in mine you would just change
input.Substring(i + 1)
to
input.Substring(0,i) + input.Substring(i + 1)
0

Commented:
You do need to make sure to have
using System.Collections
at the top to use the ArrayList or you could modify the code to use whatever collection type you prefer.
0

Middle School Assistant TeacherCommented:
The library can also do Permuations and Combinations as well...it's pretty flexible.
0

Project Engineer, ElectricalCommented:
Just last week I was solving a Permutation problem on ProjectEuler.net and came across this website. http://www.bearcave.com/random_hacks/permute.html

In particular, I found this graphic interesting, http://www.bearcave.com/random_hacks/permute_diagram.jpg

Merely implementing that, with an otter loop that iterates through removing letters solves it.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.