任何人都可以请写或给我一个链接,我可以找到C#代码来列出所有的数组以最有效的方式给出一组数字?代码为一组给定的数字生成排列C#
0
A
回答
1
不知道如何高效的这些都是,但这里有一些选择:
+1
已经看到了这些链接。似乎不是最好的解决方案。还有其他有用的链接吗? – 2009-10-28 03:01:07
+1
我的死链接:( – 2012-10-14 22:27:33
0
有一点太晚了......只是作为参考。 ..
根据我的测试,我的工具Heap's algorithm似乎给我见过最快的性能(测试对2假定非常快的算法)。
优点:
- 堆的算法(每置换单交换)
- 没有乘(像看到了网络上的一些实现)
- 内联交换
- 通用
- 没有不安全的代码
- 到位(内存使用量非常低)
- 没有模(仅第一位比较)
我执行Heap's algorithm:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
namespace WpfPermutations
{
/// <summary>
/// EO: 2016-04-14
/// Generator of all permutations of an array of anything.
/// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
/// </summary>
public static class Permutations
{
/// <summary>
/// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
/// </summary>
/// <param name="items">Items to permute in each possible ways</param>
/// <param name="funcExecuteAndTellIfShouldStop"></param>
/// <returns>Return true if cancelled</returns>
public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
{
int countOfItem = items.Length;
if (countOfItem <= 1)
{
return funcExecuteAndTellIfShouldStop(items);
}
var indexes = new int[countOfItem];
for (int i = 0; i < countOfItem; i++)
{
indexes[i] = 0;
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
for (int i = 1; i < countOfItem;)
{
if (indexes[i] < i)
{ // On the web there is an implementation with a multiplication which should be less efficient.
if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same.
{
Swap(ref items[i], ref items[indexes[i]]);
}
else
{
Swap(ref items[i], ref items[0]);
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
indexes[i]++;
i = 1;
}
else
{
indexes[i++] = 0;
}
}
return false;
}
/// <summary>
/// This function is to show a linq way but is far less efficient
/// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="length"></param>
/// <returns></returns>
static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
/// <summary>
/// Swap 2 elements of same type
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
/// <summary>
/// Func to show how to call. It does a little test for an array of 4 items.
/// </summary>
public static void Test()
{
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
Console.WriteLine("Ouellet heap's algorithm implementation");
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
Console.WriteLine("Linq algorithm");
foreach (var v in GetPermutations(values, values.Length))
{
Console.WriteLine(String.Join("", v));
}
// Performance Heap's against Linq version : huge differences
int count = 0;
values = new int[10];
for (int n = 0; n < values.Length; n++)
{
values[n] = n;
}
Stopwatch stopWatch = new Stopwatch();
ForAllPermutation(values, (vals) =>
{
foreach (var v in vals)
{
count++;
}
return false;
});
stopWatch.Stop();
Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
count = 0;
stopWatch.Reset();
stopWatch.Start();
foreach (var vals in GetPermutations(values, values.Length))
{
foreach (var v in vals)
{
count++;
}
}
stopWatch.Stop();
Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
}
}
}
使用示例:一组给定数字的排列
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
0
public static IEnumerable<T[]> Permute<T>(T[] array)
{
for(int i=0; i<array.Length; i++)
{
if (array.Length <= 1)
{
yield return array;
}
else
{
T[] except = new T[array.Length - 1];
Array.Copy(array, except, i);
Array.Copy(array, i + 1, except, i, array.Length - i - 1);
foreach (T[] sub in Permute(except))
{
T[] answer = new T[sub.Length + 1];
Array.Copy(sub, 0, answer, 1, sub.Length);
answer[0] = array[i];
yield return answer;
}
}
}
}
相关问题
- 1. 生成给定数字的数字的所有排列?
- 2. 生成给定GCD的数字列表
- 3. 为给定数字生成金字塔?
- 4. 生成总和为给定数的统一二进制数组
- 5. 生成数字的排列在一定的算法
- 6. 为一组数字生成组合
- 7. 给定一个System.Type生成类定义的源代码?
- 8. 如何根据给定的字符和长度生成一个排列列表?
- 9. C++代码生成
- 10. C#代码生成
- 11. 在D中生成给定字符串的所有排列
- 12. 生成给定字符串的有序排列
- 13. C代码排列
- 14. 如何为我的Native(C,C++)代码生成序列图?
- 15. 为给定的基数和位数生成所有可能的排列
- 16. 在LINQ中为n组生成排列
- 17. 从一个数组中生成一个排列列表
- 18. 需要在给定范围内生成一对数字C#
- 19. C#SQLMetal生成的代码
- 20. CFG生成的C#代码
- 21. 如何为给定的JBoss Drool DRL文件生成java代码?
- 22. 给C++代码给定xml:
- 23. 生成随机数的代码C++
- 24. Javascript代码为字母排列的div
- 25. 如何从代码覆盖率数字中排除browserify生成的代码?
- 26. 生成一个字符串的组合(不是排列)
- 27. 为Oracle表生成C#代码
- 28. 生成一些数字范围的所有排列序列
- 29. 生成字母数字代码的非重复列表
- 30. 从给定字符串生成一组字符串
可能重复](http://stackoverflow.com/questions/1653500/permutations-of-a-given-set-of-numbers) – mafu 2010-09-24 11:43:46