Need programming help

[aneeshm]

Can someone tell me a way to print all possible combinations of a string of letters?

Eg. if I give the input "abc", it should give the output

abc
acb
bac
bca
cab
cba

I have a rudimentary knowledge of C/C++, and a (very very) little bit of Lisp/Scheme.

[Jack_www]

I would be more than happy to help you. I love to program, and I know a lot about C++. I dont think there are any built in functions that will do that for you, but there are some that can help you do this. How long can the string be?

[Jack_www]

one way you can do this is pure force way, using loops to come up with all possible comibations of those letters. I also think that you can use a spanning tree to do this if you need something that is faster.

[aneeshm]

Say a limit of 25 characters?

I know that that would be practically impossible - it works out to 25! combinations - but I'm taking that as the theoretical maximum I'd want.

[Jack_www]

yes that would take a long time, but it would not be 25 combinations, but 25 to the 25 power of combinations . So I think spanning tree is your best bet. I need to go to sleep though, but I will look up some stuff when I get up.

[aneeshm]

We can use each letter only the number of times it appeared in the original string. If that is the case, then the number of combinations reduces to 25! (= 25x24x23x22....x1), or even less. If we are allowed to use the same element an arbitrary number of times, then it becomes 25^25.

[aneeshm]

I initially thought of a recursive function that iterates over each element, and for each element gives a string with that element removed to itself, thus resulting in the result, but I couldn't work it out.

[Thue]

Quick and dirty version in php...

$chars = Array('a', 'b', 'c');

$used_indices = Array();



gen($used_indices);



function gen(&$used_indices) {

  global $chars;



  if (sizeof($used_indices) < sizeof($chars)) {

    for ($i=0; $i
      if (!in_array($i, $used_indices)) {

        array_push($used_indices, $i);

        gen($used_indices);

        array_pop($used_indices);

      }

    }

  } else {

    for ($i=0; $i
      echo $chars[$used_indices[$i]];

    }

    echo "\n";

  }

}

[Thue]

The problem solved in ML; this solution is nicer.

This is programmed using a very functionel strategy, somewhat different from the PHP one used above. It seemed so much nicer that I tried translating it to php afterwards, but I ended up with a PHP program larger and uglier than the PHP program above.

val chars = ["a", "b", "c"];

fun gen (a::arest) bs       res = (gen (arest@bs) [] (a::res))@(gen arest (a::bs) res)
  | gen []       []       res = [res]
  | gen []       bs       res = [];

gen     chars    []       [];

[Ari Rahikkala]

Re: Need programming help

Originally posted by aneeshm
Can someone tell me a way to print all possible combinations of a string of letters?

Eg. if I give the input "abc", it should give the output

abc
acb
bac
bca
cab
cba

I have a rudimentary knowledge of C/C++, and a (very very) little bit of Lisp/Scheme.

Those are called permutations, not combinations. With that knowledge, you should be able to Google an answer in C++ easily.

[aneeshm]

*Smacks head*

Damn the incorrect terminology!

[Thue]

I would like to see a C/C++ program as short and simple as my ML program. I bet that isn't possible

[LordShiva]

WTF is ML?

[Thue]

The first programming taught to new students at the Copenhagen University of Computer Science. http://en.wikipedia.org/wiki/ML_programming_language

[Whoha]

Originally posted by LordShiva
WTF is ML?

you didn't have to take the "History of dead programming languages" course?