KojiDoiさんの回答をもとにして文字列生成まで書きました。
itertools.product
を使うと比較的簡単に記述できます。
追記を受けて
かなり泥臭いですが、異なる文字種で区切る処理も書いてみました。
Python
1import re
2import itertools
3
4# 異なる文字種で区切る
5def split(s):
6 rk = re.compile(r'([ァ-ヴ]|ー)')
7 rd = re.compile(r'[0-9]')
8 ra = re.compile(r'[a-zA-Z]')
9
10 lst = []
11 prev,cur = -1,-1
12 sub = ''
13 for c in s:
14 if rk.match(c): cur = 1
15 elif rd.match(c): cur = 2
16 elif ra.match(c): cur = 3
17 else: cur = 4
18
19 if prev > 0 and prev != cur:
20 lst.append(sub)
21 sub = ''
22 sub += c
23 prev = cur
24
25 if sub:
26 lst.append(sub)
27
28 return lst
29
30lst = split('アイウ1エオカABC')
31print(lst) # ['アイウ', '1', 'エオカ', 'ABC']
32
33ret = []
34for tpl in itertools.product(['','_'],repeat=len(lst)-1):
35 s = lst[0]
36 for t,l in zip(tpl,lst[1:]):
37 s += t + l
38 ret.append(s)
39print(ret)
40# ['アイウ1エオカABC', 'アイウ1エオカ_ABC', 'アイウ1_エオカABC', 'アイウ1_エオカ_ABC', 'アイウ_1エオカABC', 'アイウ_1エオ カ_ABC', 'アイウ_1_エオカABC', 'アイウ_1_エオカ_ABC']