高手进来看看求全部组合问题

问大家个问题，如何列出串中全部组合。
如：1249，4可以变为3，4，6，而9可以变为7，8，9.全部组合为：1239，1249，1269，1237，1238，1247，1248，1267，1268
谁能给出好的想法。
目前的情况是：
1 串的长度不确定，可能很长，内存是否够用的问题。 
2 我能想到的处理方式为：遍历到第1个4的时候，我生成了3个，（3，4，6）然后需要对每个子串，再进行后面的循环遍历。这么处理太累，不知道什么时候停止，解空间一直在扩展。
3 有没有比较好的处理方式？尽可能的优化？

如何写出这个递归函数。小弟，在此谢谢各位大侠了。

google一下组合