求個演算法，M個數，取N個排列，N>M
比如有數字，1，2，3，取4個進行排列。
結果如下：
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3
不可以重復，順序可以任意。
uj5u.com熱心網友回復：
這種費腦袋的看來都不愿意想啊uj5u.com熱心網友回復：
對啊，不想廢腦筋。把你的題目換成，大家一眼就明白的，你自己就可以做
12取3，你覺著呢？？ 一個鐘表表盤，時分秒3個指標，12小時，轉一圈下來，是不是全排列了，是不是不會重復
所以，自己按照鐘表那么寫就好，秒針轉一圈，分針進1位，分針轉一圈，時針進一位
說白了就是N進制拉
uj5u.com熱心網友回復：
兩個回圈解決的事uj5u.com熱心網友回復：
O(n^m) 遞回,n=3,m=4，得到81個數。不會遞回直接寫4層回圈。
uj5u.com熱心網友回復：
這樣把，如果樓主還看不清，我們換個更簡單直白的說法0，1，2，3，4，5，6，7，9
取3位
無非就是
000
001
002
003
-----
009
010
------
999
他全排沒有，重復沒有
至于啥N>M，其實完全就是個障眼法，根本就不值得考慮
N>M 是把？也就是用N當進制而已，不用M當進制， 你該怎么進位就怎么進位，無非是 最后顯示的時候 取個余數（模），也就是 當前位的值%M
uj5u.com熱心網友回復：
哦，的確是個障眼法，我也迷了，不過結論正確，壓根不值得考慮上面被迷，修復一下，還是M進制
誰說10進制數不能表達11位資料了，所以壓根不要去考慮撒N》M，這條件就是用來迷惑人的
uj5u.com熱心網友回復：
神仙打架，哈哈，到 底幾個回圈
uj5u.com熱心網友回復：
謝謝回復。
uj5u.com熱心網友回復：
M>N,還是M<N，是有點說法的，實作起來還真不是一樣的
uj5u.com熱心網友回復：
對于 M個數，取N個排列，N>MN>M 是錯誤的條件 因為條件沒有滿足的機會
寫作 M個數，取N個排列，M>N
你可以先求組合，在對組合的結果求 排列
求排列和組合 的代碼有很多，是程式員的永久話題，因為效率總是第一位的
uj5u.com熱心網友回復：
沒你想的那么復雜，你弄明白了，他就是進位隨便寫，反正要放假了，無心寫代碼，俺就隨手寫一個，也不講究啥效率，性能，最優。你看看，到底所謂的N，M大小對你實作有沒有啥區別，反正對于我下面的代碼來說，沒有任何區別
test test = new test(3, 4);
int[] dic = new int[] { 1, 2, 3 };
do
{
Console.WriteLine(string.Join(",", test.GetCcurentIndex().Reverse().Select(p => dic[p])));
} while (test.Increment());
public class test
{
private readonly int _m;
private readonly int _n;
private node nodel;
public test(int M, int N)
{
_m = M;
_n = N;
nodel = new node(M);
node ccurentnode = nodel;
for (int i = 0; i < _n - 1; i++)
{
node tempnode = new node(M);
ccurentnode.parent = tempnode;
ccurentnode = tempnode;
}
}
public bool Increment()
{
var lst = GetCcurentIndex();
if (!lst.All(p => p == _m - 1))
{
nodel.Increment();
return true;
}
else
{
return false;
}
}
public IEnumerable<int> GetCcurentIndex()
{
return Show(nodel);
}
private IEnumerable<int> Show(node node)
{
yield return node.Value;
if (node.parent != null)
{
var temp = Show(node.parent);
foreach (var item in temp)
{
yield return item;
}
}
else
{
yield break;
}
}
//位node
public class node
{
private readonly int _n;
public int Value { get; set; } = 0;
public node parent { get; set; }
public node(int N)
{
_n = N;
}
//模擬+1，判定是否要進位
public void Increment()
{
Value = Value + 1;
if (Value == _n)
{
parent?.Increment();
}
Value = Value % _n;
}
}
}
運行結果
1,1,1,1
1,1,1,2
1,1,1,3
1,1,2,1
1,1,2,2
1,1,2,3
1,1,3,1
1,1,3,2
1,1,3,3
1,2,1,1
1,2,1,2
1,2,1,3
1,2,2,1
1,2,2,2
1,2,2,3
1,2,3,1
1,2,3,2
1,2,3,3
1,3,1,1
1,3,1,2
1,3,1,3
1,3,2,1
1,3,2,2
1,3,2,3
1,3,3,1
1,3,3,2
1,3,3,3
2,1,1,1
2,1,1,2
2,1,1,3
2,1,2,1
2,1,2,2
2,1,2,3
2,1,3,1
2,1,3,2
2,1,3,3
2,2,1,1
2,2,1,2
2,2,1,3
2,2,2,1
2,2,2,2
2,2,2,3
2,2,3,1
2,2,3,2
2,2,3,3
2,3,1,1
2,3,1,2
2,3,1,3
2,3,2,1
2,3,2,2
2,3,2,3
2,3,3,1
2,3,3,2
2,3,3,3
3,1,1,1
3,1,1,2
3,1,1,3
3,1,2,1
3,1,2,2
3,1,2,3
3,1,3,1
3,1,3,2
3,1,3,3
3,2,1,1
3,2,1,2
3,2,1,3
3,2,2,1
3,2,2,2
3,2,2,3
3,2,3,1
3,2,3,2
3,2,3,3
3,3,1,1
3,3,1,2
3,3,1,3
3,3,2,1
3,3,2,2
3,3,2,3
3,3,3,1
3,3,3,2
3,3,3,3
uj5u.com熱心網友回復：
首先謝謝啊，真是辛苦了。但對果不對啊，
要求有一條是，不能重復，
1,1,1,2 和2,1,1,1是重復的。。。
像你說的，只在最后一位加1，不停的向前進位即可。
uj5u.com熱心網友回復：
額，這到底求排列啊，還是求組合？？？1,1,1,2 和2,1,1,1是重復的。也就是這2個相等，這是組合好吧
我還真懶寫了，你把這81個按余弦相似度做個Distinct就是結果了
uj5u.com熱心網友回復：
demo:
int[] array = {1, 2, 3, 4};
int a1, a2, a3, a4;
int iCount = 0;
for (int i1 = 0; i1 < array.Length; i1++)
{
for (int i2 = 0; i2 < array.Length; i2++)
{
if (i2 == i1)
{
continue;
}
for (int i3 = 0; i3 < array.Length; i3++)
{
if (i3 == i1 || i3 == i2)
{
continue;
}
for (int i4 = 0; i4 < array.Length; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3)
{
continue;
}
a1 = array[i1];
a2 = array[i2];
a3 = array[i3];
a4 = array[i4];
iCount++;
Console.WriteLine("{0}-{1}-{2}-{3}", a1, a2, a3, a4);
}
}
}
}
Console.WriteLine("AllCount == {0}", iCount);
Console.ReadKey();
}
uj5u.com熱心網友回復：
“N>M 是錯誤的條件 因為條件沒有滿足的機會 ”你這句話就說錯啦，除了M等于1之外，其他情況都能滿足uj5u.com熱心網友回復：
P(M,N) 是 從 M 個 元素中取 N個做排列那么 你能從 4 個數中取出 5 個數嗎
uj5u.com熱心網友回復：
很簡單，十幾行代碼的事。
def next(indexes, m, n):
for i in range(n):
index = indexes[i]
# find the first one that can be increased
if index < m-1:
# fill 0 .. i with the increased value
for j in range(i+1):
indexes[j] = index+1
return True
return False
def indexToNum(index, num):
return [num[i] for i in index]
nums = [1,2,3]
indexes = [0,0,0,0]
print(indexToNum(indexes, nums))
while next(indexes, 3, 4):
print(indexToNum(indexes, nums))
'''Output
[1, 1, 1, 1]
[2, 1, 1, 1]
[3, 1, 1, 1]
[2, 2, 1, 1]
[3, 2, 1, 1]
[3, 3, 1, 1]
[2, 2, 2, 1]
[3, 2, 2, 1]
[3, 3, 2, 1]
[3, 3, 3, 1]
[2, 2, 2, 2]
[3, 2, 2, 2]
[3, 3, 2, 2]
[3, 3, 3, 2]
[3, 3, 3, 3]'''
uj5u.com熱心網友回復：
https://blog.csdn.net/goldenhawking/article/details/80037669轉載請註明出處，本文鏈接：https://www.uj5u.com/net/281985.html
標籤：C#