|
Wait, are your integers 64bits long? That changes some things, such as the limits.
You can, with 32bit integers and arithmetic shifts, use
x -= ((x - 290) >> 31);
Will work from x = -2147483358 to x = 290.
For 64bit integers and arithmetic shifts:
x -= ((x - 290) >> 63);
Will probably work from x = 0x8000000000000122 to x = 290, but I haven't tried it.
(the third way, of course, has higher upper limits)
The number had to be greater than 0x80000006 (or 0x80000121 in this case) because otherwise for lower x (there are very few values lower than that, of course), subtracting 7 (290 in this case) would overflow. That usually results in wrapping to a positive number (thus destroying the mask), or, because signed overflow is actually UB in C++, it could do something .. unspecified, which is also not a good thing. The first reasons makes it so that you can't cast to unsigned to do the subtraction to get rid of the UB and thereby fix the problem - you can absolutely cast to unsigned to do the subtraction and that would get rid of the UB, but it wouldn't fix the problem.
modified 20-Nov-13 12:37pm.
|
|
|
|
|
Thank you,it's 32bit word
|
|
|
|
|
The spiral function f(n),
maps a non-negative integer n onto an ordered pair of integers ¡
x(n), y(n)
. For example, it maps n = 9 onto the ordered pair (1; 2)
11 10 9
2 1 8
3 0 7
4 5 6
0<=n<=1000
is there any direct mapping function or I have to use looping..?
i thing there is direct mapping function because question is from "Concrete Mathematics"
|
|
|
|
|
Never heard of that function. Can you tell us more about it?
|
|
|
|
|
The first step is the observation that the number of non-edge numbers (in the center block) is always an odd number squared.
E.g. for 1-8, it's the single number, 0, which is 1 squared. For 9-24, it's 3 squared (the nine digits 0-8).
So you find the largest odd square that can be subtracted from n without going negative. The remainder gives the position on the edge, starting from the position above the upper-right corner of the center block.
|
|
|
|
|
I need a test input file for a function I'm developing - no problem I thought, I'll quickly whip one up in Excel and get on with it. I've now been trying to create the test file for three days!
It seems so simple, but probability appears to be working against me!
I need a 1000x1000 symmetric matrix with 49 'random' ones in each column, filled in reciprocally to make the thing symmetrical. Obviously as you come to the bottom corner of the matrix the available 'random' slots start to run out. Nevermind I thought, I'll wait until my code gets to the hard bit, stop it and then fill in the missing bits by hand.
Unfortunately, I always seem to be left with an insoluble problem - I can't fill in the column, because (somehow) the reciprocal spaces I 'need' have already been used. I'm sure I've made some elementary mistake, but I just can't spot it.
Can anyone fix my code? (Or come up with an algorithm that works!)
Ugly hacky VBA below:
Option Explicit
Public Sub CreateRandomPeers()
Dim TotalEntries As Integer
Dim colEnd As Integer
Dim rowEnd As Integer
Dim colStart As Integer
Dim rowStart As Integer
Dim curCol As Integer
Dim curRow As Integer
Dim curEntries As Integer
Dim rndEntries As Integer
Dim rndRow As Integer
Dim count As Integer
Dim colcnt As Integer
Dim i As Integer, j As Integer
Dim row As Integer
Dim col As Integer
Dim calcmode As XlCalculation
TotalEntries = 49
colEnd = 1001
rowEnd = 1001
colStart = 2
rowStart = 2
calcmode = Application.Calculation
Application.Calculation = xlCalculationAutomatic
curRow = rowStart
For curCol = colStart To colEnd Step 1
curPeers = 0
For i = rowStart To rowEnd Step 1
If (Application.Cells(i, curCol) = 1) Then
curEntries = curEntries + 1
End If
Next i
rndEntries = TotalEntries - curEntries
Randomize
count = 0
While (count < rndEntries)
DoEvents
rndRow = CInt(Int((rowEnd - rowStart + 1) * Rnd())) + rowStart
If (rndRow <> curCol) Then
If (Application.Cells(rndRow, curCol) = 0) Then
colcnt = 0
For j = rowStart To rowEnd Step 1
colcnt = colcnt + Application.Cells(j, rndRow)
Next j
If (colcnt < TotalEntries) Then
Application.Cells(rndRow, curCol) = 1
Application.Cells(curCol, rndRow) = 1
count = count + 1
End If
End If
End If
Wend
Next curCol
Application.Calculation = calcmode
End Sub
Public Sub Reset()
Application.Range("B2:ALM1001") = 0
Application.Calculation = xlCalculationAutomatic
End Sub
modified 29-Oct-13 20:00pm.
|
|
|
|
|
The matrix you are creating would have zeroes on the diagonal, and then you insert "1's" at random on #49 pairs of "symmetric" cells of the form cell[i,j] = 1, and cell[j,i] = 1 ?
One thing that "jumped out" at me reading your code:
rndEntries = TotalEntries - curEntries I can't see 'TotalEntries being initialized to any value in your code; is it possible that 'TotalEntries should be: 'TotalPeers ?
thanks, Bill
Google CEO, Erich Schmidt: "I keep asking for a product called Serendipity. This product would have access to everything ever written or recorded, know everything the user ever worked on and saved to his or her personal hard drive, and know a whole lot about the user's tastes, friends and predilections." 2004, USA Today interview
modified 29-Oct-13 11:59am.
|
|
|
|
|
Yeah, TotalEntries should be 49, edited to fix
|
|
|
|
|
Hey guys!
Recently I posted this question "Picking entities from a group[^]" on the codeproject. I was advised to move it to this forum because some of you clever ones may have a way to go.
My problem is that I have a group of n people (in my example I said 8 but let's say a minimum of four). I want each person in the group to point to a different person in the group. This means no person can point to himself. Also if a person points to some person in the group, no other person in the group can point to the same person. So everyone in the group must point to a person, and everyone in the group is pointed at. I also want the process to be random.
For now I've already done this by creating a generic list of 'allowed' persons, pick a random person from the list, remove that person from the list and so on.
Now here comes the difficult part..
I also want to be able to configure impossible combinations. Like Person A cannot point to Person B and Person B cannot point to Person A.
This makes the process way more difficult. I'd like to have the ability to test whether a certain configuration is possible and to only pick between these possible 'combination sets'.
My solution now, is a trial on error method. I start a large loop and start to random picking just like above. I generate a list of possibilities and pick one of the possibilities. If the list of possibilities happens to be empty, that means I ran into an impossible 'combination set' and start the entire process again. If the picking fails a certain number of times, I assume the configuration is impossible.
As you understand my solution for now isn't ideal, 'cause there's no way to check whether a configuration is possible and if my picking routine tells me the configuration is not possible you're not actually sure the config is not possible.
I think I got my problem explained well as my English is fairly good but way from perfect. Hope you guys can point me in a good direction.
Thanks! Eduard
.: I love it when a plan comes together :.
|
|
|
|
|
|
This sounds like a type of directed[^] graph[^] with indegree and outdegree 1. It has similarities to the Hamiltonian path problem[^], except that you could have multiple disconnected paths within the same graph.
Not sure if that helps at all, or just confuses the problem! Hopefully, it might give you somewhere to start looking.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Here's another way of thinking about this:
You have an array of values. The index into the array is the zero-based number of the person doing the pointing, and the value is the zero-based index of the person being pointed at. This automatically satisfies the rule that each person can only point to one other person. You then only need to validate that nobody is pointing to themselves, nobody is pointing to a forbidden person, and there are no duplicates.
public struct ForbiddenConnection
{
private readonly int _source;
private readonly int[] _destination;
private ForbiddenConnection(int source, int[] destination)
{
_source = source;
_destination = destination;
}
public static ForbiddenConnection Create(int source, IEnumerable<int> destination)
{
return new ForbiddenConnection(source, SortedDistinct(destination).ToArray());
}
public static ForbiddenConnection Create(int source, params int[] destination)
{
return Create(source, destination.AsEnumerable());
}
private static IEnumerable<int> SortedDistinct(IEnumerable<int> source)
{
if (source == null) yield break;
bool started = false;
int lastItem = 0;
foreach (int item in source.OrderBy(x => x))
{
if (started && item == lastItem) continue;
yield return item;
lastItem = item;
started = true;
}
}
public int Source
{
get { return _source; }
}
public bool Contains(int destination)
{
return _destination != null && Array.BinarySearch(_destination, destination) >= 0;
}
}
public sealed class GraphGenerator : IEnumerable<IReadOnlyList<int>>
{
private readonly int _length;
private readonly IDictionary<int, ForbiddenConnection> _forbidden;
private GraphGenerator(int length, IEnumerable<ForbiddenConnection> forbidden)
{
_length = length;
if (forbidden != null)
{
_forbidden = forbidden.ToDictionary(fc => fc.Source);
}
else
{
_forbidden = new Dictionary<int, ForbiddenConnection>(0);
}
}
public static GraphGenerator Create(int length, IEnumerable<ForbiddenConnection> forbidden)
{
if (length < 2) throw new ArgumentOutOfRangeException("length");
return new GraphGenerator(length, forbidden);
}
public static GraphGenerator Create(int length, params ForbiddenConnection[] forbidden)
{
return Create(length, forbidden.AsEnumerable());
}
private bool Validate(IReadOnlyList<int> graph)
{
Debug.Assert(graph != null);
Debug.Assert(graph.Count == _length);
for (int i = 0; i < graph.Count; i++)
{
int index = graph[i];
Debug.Assert(0 <= index && index < _length);
if (index == i)
{
Trace.TraceInformation("Node {0} points to itself.", i);
return false;
}
ForbiddenConnection forbidden;
if (_forbidden.TryGetValue(i, out forbidden) && forbidden.Contains(index))
{
Trace.TraceInformation("Node {0} cannot point to node {1}.", i, index);
return false;
}
for (int j = i + 1; j < graph.Count; j++)
{
if (graph[j] == index)
{
Trace.TraceInformation("Nodes {0} and {1} both point to node {2}.", i, j, index);
return false;
}
}
}
return true;
}
public IEnumerator<IReadOnlyList<int>> GetEnumerator()
{
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
Now you just need to generate every permutation of indices for your graph, and return those which are valid. Eric Lippert has an excellent seven-part series on generating permutations[^], so we can borrow some of his code:
public struct Permutation : IReadOnlyList<int>
{
public static readonly Permutation Empty = default(Permutation);
private readonly int[] _value;
private Permutation(Permutation source, int index, int value)
{
if (source.Count == 0)
{
_value = new[] { value };
}
else
{
_value = new int[source.Count + 1];
_value[index] = value;
if (index != 0)
{
Array.Copy(source._value, 0, _value, 0, index);
}
if (index != source.Count)
{
Array.Copy(source._value, index, _value, index + 1, source.Count - index);
}
}
}
public int Count
{
get { return (_value == null) ? 0 : _value.Length; }
}
public int this[int index]
{
get
{
if (0 > index || index >= Count) throw new ArgumentOutOfRangeException("index");
return _value[index];
}
}
public IEnumerator<int> GetEnumerator()
{
if (_value == null) return Enumerable.Empty<int>().GetEnumerator();
return _value.AsEnumerable().GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public static IEnumerable<Permutation> HamiltonianPermutations(int ofSize)
{
if (ofSize < 0) throw new ArgumentOutOfRangeException("ofSize");
return HamiltonianPermutationsIterator(ofSize);
}
private static IEnumerable<Permutation> HamiltonianPermutationsIterator(int ofSize)
{
if (ofSize == 0)
{
yield return Empty;
yield break;
}
bool forwards = false;
foreach (var permutation in HamiltonianPermutationsIterator(ofSize - 1))
{
for (int index = 0; index < ofSize; index++)
{
int insertAt = forwards ? index : ofSize - index - 1;
yield return new Permutation(permutation, insertAt, ofSize - 1);
}
forwards = !forwards;
}
}
}
This leads to a very simple implementation of the GraphGenerator.GetEnumerator method:
public IEnumerator<IReadOnlyList<int>> GetEnumerator()
{
return Permutation.HamiltonianPermutations(_length)
.Cast<IReadOnlyList<int>>()
.Where(Validate)
.GetEnumerator();
}
Using it would look something like this:
var generator = GraphGenerator.Create(8,
ForbiddenConnection.Create(0, 1),
ForbiddenConnection.Create(1, 0)
);
if (!generator.Any())
{
}
For eight people with no forbidden connections, there are 14833 possible graphs. On my computer, enumerating every possible graph takes approximately 0.11 seconds, which should be fast enough for most purposes.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Upvoted.
What a fascinating answer ! I look forward to studying this code.
thanks, Bill
Google CEO, Erich Schmidt: "I keep asking for a product called Serendipity. This product would have access to everything ever written or recorded, know everything the user ever worked on and saved to his or her personal hard drive, and know a whole lot about the user's tastes, friends and predilections." 2004, USA Today interview
|
|
|
|
|
I'm using "system.speech" library to recognize voice commands, but I want to use genetic algorithms to improve recognition, and I'm new to GAs and I've some questions:
How to implement this (what is the population in this situation? the genomes..)
Can this be done using the c# speech recognition library or should I use FFT....
Any other advice ll be apprecited. Thank you
modified 15-Oct-13 10:21am.
|
|
|
|
|
The current thinking is to calculate hash for every file ,and then delete them.
Now we can use MD5 or SHA1 to calculate hash.From the speed point of view, MD4 is a better choice when MD4 is faster but more unsafer.But after experiment, i found even md4 is so slow that it would cost a lot of time when i dealt with large files.
So any algorithm to work faster?
|
|
|
|
|
If the name and size are the same, then delete them.
|
|
|
|
|
yeah ,it is a good idea.
Another situation is that -The contents of file is the same but names are different.
And i want to know which kind of hash algorithm has the best speed?
or any other way to speed up?
|
|
|
|
|
You can considerably speed up the process: If you have mostly big files you can use a two step hash comparison. In the first step you take only say 1 - 5 KB from the beginning of the file to build your hash (I'd recommend SHA2[^]). You only perform a hash calculation for the complete file if the hashes for two files match.
Best,
Manfred
"I had the right to remain silent, but I didn't have the ability!"
Ron White, Comedian
|
|
|
|
|
Thanks for your advice.
However i wonder why SHA2 should be a better choice which is slower than MD5 or MD4?
|
|
|
|
|
It's been developed to be more robust, i.e. the probability to have collisions is reduced.
Just look it up, there are plenty of good explanations on the internet on what the actual improvements over its predecessors are.
Cheers!
"I had the right to remain silent, but I didn't have the ability!"
Ron White, Comedian
|
|
|
|
|
|
i found a similar solution when i had to recover 4.5TB of files mostly between .5 - 15GB where around 1-2% of them were early terminated during a copy process, but left with correct filesize filled up with zeroes.
it adds to your suggestion to scan all big files with big fixed and some random jumps up to their ends.
|
|
|
|
|
It is almost sure that the problem not your hash algorithm but I/O. All (most) hash algorithms are short and fast enough to not blame them...
If you have large number of files you have to rethink your approach.
1. use file system's FileInfo - name, size, creation, last modified and so
2. if you can't you may consider to hash only the first block (4K) of every file and go forward only for those found the same.
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is (V).
|
|
|
|
|
Thank you V. ^_^
Your advice is good. In the beginning i had not a clear understanding of this question.
Now i agree I/O should be the key point, and i wish i can find a way to resolve my problem.
Thanks!
|
|
|
|
|
Yes I/O is a key issue...
If it is in your power you may move the storage to a more capable one, like SCSI or flash, that should speed up I/O...
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is (V).
|
|
|
|
|