0

I want to solve an algorithm in which I have this input :

n = 30 and st = 1234321

Now i want to see how many combination's can be formed using the string i.e. it can have

(1 2 3 4 2 1)
(1 23 4 3 2 1)
(1 2 3 4 3 21)
(12 3 4 3 2 1)
(12 3 4 3 21)
(1 23 4 3 21)

i.e. all less than 30. So total combinations will be 6.

But we dicard the string in counts when we have either 0 present alone or as in leading like 09.

take the case: n = 70 and st = 8675309. Now in this case we have:

(8 6 7 5 3 0 9)
(8 67 5 3 0 9)
(8 6 7 53 0 9)
(8 6 7 5 30 9)
(8 6 7 5 3 09)
(8 67 53 0 9)
(8 67 5 30 9)
(8 67 5 3 09)

here count total is 2 only as (we don't count if we have either 0 present alone or as in leading like 09).

Please suggest me c# code for to find such combinations.

Improve this question
2
  • What have you tried? BTW I removed your tag for asp.net since the question in no way is specific to web development. Commented Jan 29, 2012 at 3:39
  • possible duplicate of Permutation of a list of strings algorithm Commented Jan 29, 2012 at 20:56

3 Answers 3

Reset to default
4

You can model your space as a binary tree: on the nth level, the left child joins the nth and n+1th numbers in the list, and the right child doesn't. Use DFS and prune branches that are illegal by your constraints, then count the leaf nodes.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

+1 - Great job explaining the algorithm without giving any code (Though it sounds like the OP would rather take the code).
I spent 90% of my energy on that deciphering the question, so I wrote as complete of an answer I could with what I had left.
No, no, no, I commend you for providing a coherent response to a less than complete question. The OP showed very little effort in writing their (very cryptic and ambiguous) question. The answer should not contain code. My point was that they would probably prefer that it did considering the wording of the question.
@bdares : Please give me some code for the 1st half of the question i.e. just counting for 1st case n = 30 and st = 1234321 I will handle for presence of 0.
@ItsLockedOut - SO is not a Rent-a-Coder site. If you want source code, write it yourself and ask us questions along the way, or pay someone to write the code for you.
0

Here is a link to a tutorial and code for a string permutation class in C#. I am not going to transpose your numbers into this code for you because it is very straight forward.

Good luck!

Improve this answer

1 Comment

If you look a bit more carefully at the question, you will see that he's not interested in permutations of the elements, but rather concatenations of them.
0

It's a simple problem, the only part that's unique is that you need to calculate all your sub string values and get the unique values before then finding all the combinations that then add up to less than 60.

1) Get all unique sub string values
2) Get all permutations for these values
3) then remove any that add up to be over 60
4) do step 2 again

Steps 2 to 4 are discussed here

Performance will suck a little compared to using a tree but not greatly for small length starting strings.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.